沿直线排列着 $N$ 个天线，编号为 $1$ 到 $N$。每两个相邻天线之间的距离为 $1$ 公里。天线 $i$ ($1 \le i \le N$) 的高度为 $H_i$。天线 $i$ 可以向距离其 $A_i$ 公里到 $B_i$ 公里（含边界）范围内的天线发送信息。当且仅当天线 $x$ 和天线 $y$ ($1 \le x < y \le N$) 能够互相发送信息时，称这对天线处于通信状态，其通信代价为 $|H_x - H_y|$。

JOI 共和国总理 K 先生收到了 $Q$ 条关于连接不良的市民投诉。研究表明，对于第 $j$ 条投诉 ($1 \le j \le Q$)，天线 $L_j, L_j + 1, \dots, R_j$ 之间存在故障。你需要判断在天线 $L_j, L_j + 1, \dots, R_j$ 中是否存在处于通信状态的天线对，如果存在，还需要找出这些天线对中的最大通信代价。

编写一个程序，给定天线信息和投诉信息，判断在天线 $L_j, L_j + 1, \dots, R_j$ 中是否存在处于通信状态的天线对，并在存在此类天线对时计算其中的最大通信代价。

输入格式

从标准输入读取以下数据。所有输入值均为整数。

$N$ $H_1$ $A_1$ $B_1$ $\vdots$ $H_N$ $A_N$ $B_N$ $Q$ $L_1$ $R_1$ $\vdots$ $L_Q$ $R_Q$

输出格式

输出 $Q$ 行到标准输出。第 $j$ 行 ($1 \le j \le Q$) 应输出在天线 $L_j, L_j + 1, \dots, R_j$ 中不存在处于通信状态的天线对时的 $-1$，否则输出这些天线对中的最大通信代价。

数据范围

• $2 \le N \le 200\,000$
• $1 \le H_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $1 \le A_i \le B_i \le N - 1$ ($1 \le i \le N$)
• $1 \le Q \le 200\,000$
• $1 \le L_j < R_j \le N$ ($1 \le j \le Q$)

子任务

1. (2 分) $N \le 300, Q \le 300$
2. (11 分) $N \le 2\,000$
3. (22 分) $Q = 1, L_1 = 1, R_1 = N$
4. (65 分) 无附加限制

样例

样例输入 1

5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5

样例输出 1

-1
1
8
8
99

说明 1

天线 $1$ 和天线 $2$ 不处于通信状态，因此第 $1$ 条投诉的答案为 $-1$。 第 $2, 3, 4, 5$ 条投诉中，具有最大通信代价的处于通信状态的天线对分别为 $(2, 3), (1, 3), (1, 3)$ 和 $(4, 5)$。

样例输入 2

20
260055884 2 15
737689751 5 5
575359903 1 15
341907415 14 14
162026576 9 19
55126745 10 19
95712405 11 14
416027186 8 13
370819848 11 14
629309664 4 13
822713895 5 15
390716905 13 17
577166133 8 19
195931195 10 17
377030463 14 17
968486685 11 19
963040581 4 10
566835557 1 12
586336111 6 16
385865831 8 9
1
1 20

样例输出 2

806460109

说明 2

该样例输入满足子任务 3 的限制。