满员电车

Problem Description

小 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$ 号站台上车的时刻。

Input

第一行包含一个正整数 $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$。

Output

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

Sample Input

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

Sample Output

5
30
15
51
61
20
-1

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（7）