Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:512 MB
统计

题目描述

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