题目描述
有 $n$ 棵待考察的小行星从左到右排成一排,且相邻两颗小行星的距离为 $1$。第 $i$ 颗小行星有一个亮度值 $x_i$ 和区分度 $l_i,r_i(l_i \leq r_i)$。对于小行星 $i,j(i
现在苍会不断进行摄像来考察这些小行星。具体而言,每次摄像,会包含一段区间的小行星。你需要回答,在这一段区间中,任意一对可区分的小行星的最大亮度差。如果不存在一对可区分的小行星,报告无解。
输入格式
第一行一个整数 $n$。
后面 $n$ 行每行三个整数 $x_i,l_i,r_i$ 表示一颗小行星的特征。
后面一行一个整数 $m$ 表示摄像次数。
后面一行 $m$ 行每行 $L,R$ 表示摄像的区间 $[L,R]$。
输出格式
对于每次摄像,输出一行一个整数:如果存在可区分的小行星,输出最大亮度差;否则输出 $-1$。
样例
样例输入 1
5
1 2 4
2 1 2
3 1 4
4 2 3
8 1 2
5
1 1
1 3
2 4
3 5
1 5
样例输出 1
-1
2
2
5
5
样例解释 1
在第五次摄像中,小行星 $3,5$ 可区分,亮度差为 $5$。
样例输入输出 2
见下发文件 c.in/ans
,次样例满足 Subtask1 的限制。
样例输入输出 3
见下发文件 c.in/ans
,次样例满足 Subtask4 的限制。
数据范围
Subtask1 (20pts) $n,m \leq 300$。
Subtask2 (25pts) $n \leq 2000$。
Subtask3 (25pts) $m=1,L=1,R=n$。
Subtask4 (30pts) 无特殊限制。
对于所有数据,满足 $2 \leq n,m \leq 2 \times 10^5,1 \leq l_i \leq r_i \leq n,1\leq L_i \leq R_i \leq n,1 \leq x_i \leq 10^9$