题目描述

有 $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$