小 $Q$ 每个工作日都需要搭乘电车进行通勤。仅有的一条双向电车线路包含 $n$ 个站台，沿途依次编号为 $1,2,\dots ,n$，$i$ 号站台与 $1$ 号站台的距离为 $d_i$。一共有两类电车：由 $1$ 号站台开往 $n$ 号站台的正向电车以及由 $n$ 号站台开往 $1$ 号站台的逆向电车。

每天从早到晚一共有 $m$ 个班次的正向电车，第 $i$ 个班次的正向电车固定在时刻 $a_i$ 从 $1$ 号站台开出，在 $a_i+d_j$ 时刻停靠 $j$ $(1\leq j\leq n)$ 号站台。换句话说，乘客能在 $j$ 号站台上车当且仅当他在时刻 $a_i+d_j$ 位于 $j$ 号站台。你可以认为恰好在时刻 $a_i+d_j$ 在 $j$ 号站台下车的乘客也可以赶上这趟换乘电车。

同理，每天从早到晚一共有 $p$ 个班次的逆向电车，第 $i$ 个班次的逆向电车固定在时刻 $b_i$ 从 $n$ 号站台开出，在 $b_i+d_n-d_j$ 时刻停靠 $j$ $(1\leq j\leq n)$ 号站台。

每天早晨，小 $Q$ 将来到家旁边的 $S$ 号站台，搭乘电车到达公司旁边的 $T$ $(S<T)$ 号站台。早高峰的电车非常拥挤，但是规律可循，对于每个班次的电车，都存在一个区间 $[l,r]$，表示当且仅当这班电车停靠 $k$ $(l\leq k\leq r)$ 号站台时是不拥挤的，此时小 $Q$ 才可以上车。但是只要小 $Q$ 上了车，就能在任意一站下车，无论是否拥挤。

小 $Q$ 可以通过换乘多趟电车的方式辗转完成通勤。请写一个程序找到最优的通勤路线，使得通勤时间最少。在这里，通勤时间定义为小 $Q$ 最终在 $T$ 号站台下车的时刻减去小 $Q$ 第一次在 $S$ 号站台上车的时刻。

输入格式

第一行包含一个正整数 $T$ $(1\leq T\leq 300)$，表示测试数据的组数。

每组数据第一行包含四个正整数 $n,m,p,q$ $(2\leq n\leq 200,000, 1\leq m,p,q\leq 200,000)$，分别表示站台、正向电车、逆向电车以及询问的数量。

第二行包含 $n$ 个整数 $d_1,d_2,\dots ,d_n$ $(0\leq d_i\leq 10^8, d_1=0, d_i<d_{i+1})$，分别表示每个站台到 $1$ 号站台的距离。

接下来 $m$ 行，每行三个整数 $a_i,l_i,r_i$ $ (0\leq a_i\leq 10^8, a_i<a_{i+1}, 1\leq l_i\leq r_i\leq n)$，依次描述每个班次的正向电车。

接下来 $p$ 行，每行三个整数 $b_i,l_i,r_i$ $ (0\leq b_i\leq 10^8, b_i<b_{i+1}, 1\leq l_i\leq r_i\leq n)$，依次描述每个班次的逆向电车。

接下来 $q$ 行，每行两个正整数 $S_i,T_i$ $(1\leq S_i<T_i\leq n)$，分别表示每个询问的起点站与终点站。

输入数据保证 $\sum n\leq 1,000,000, \sum m\leq 1,000,000, \sum p\leq 1,000,000$ 且 $\sum q\leq 1,000,000$。

输出格式

对于每个询问输出一行一个整数，即从 $S_i$ 到 $T_i$ 的最少通勤时间，若无解请输出 “-1”。

样例

输入

2
6 4 4 5
0 5 10 20 25 30
1 1 3
5 2 3
9 1 2
50 1 1
10 1 6
14 1 6
19 6 6
25 1 6
1 2
1 6
3 5
4 5
5 6
3 1 1 2
0 20 100
1 1 1
100 1 3
1 2
2 3

输出

5
30
15
51
61
20
-1