[APIO2018] 新家

题目背景

警告！滥用本题者封号！请勿多次重复提交！

题目描述

五福街是一条笔直的道路，这条道路可以看成一个数轴，街上每个建筑物的坐标都可以用一个整数来表示。小明是一位时光旅行者，他知道在这条街上，在过去现在和未来共有 $n$个商店出现。第 $i$个商店可以使用四个整数 $x_i, t_i, a_i, b_i$描述，它们分别表示：商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。

小明希望通过时光旅行，选择一个合适的时间，住在五福街上的某个地方。他给出了一份他可能选择的列表，上面包括了 $q$个询问，每个询问用二元组 （坐标，时间）表示。第 $i$对二元组用两个整数 $l_i, y_i$描述，分别表示选择的地点 $l_i$和年份 $y_i$。

现在，他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为：在居住的年份，离居住点最远的商店类型到居住点的距离。类型 $t$的商店到居住点的距离定义为：在指定的年份，类型 $t$的所有营业的商店中，到居住点距离最近的一家到居住点的距离。我们说编号为 $i$的商店在第 $y$年在营业当且仅当 $a_i ≤ y ≤ b_i$ 。注意，在某些年份中，可能在五福街上并非所有 $k$种类型的商店都有至少一家在营业。在这种情况下，不方便指数定义为 $-1$。

你的任务是帮助小明求出每对（坐标，时间）二元组居住的不方便指数。

输入格式

第一行包含三个整数 $n, k$和 $q$ ，分别表示商店的数量、商店类型的数量和（坐标，时间）二元组的数量。$(1 \leq n, q \leq 3×10^5, 1 ≤ k ≤ n)$。

接下来 $n$行，每行包含四个整数 $x_i, t_i, a_i$ 和 $b_i$用于描述一家商店，意义如题面所述$(1 ≤ x_i, a_i, b_i ≤ 10^8, 1 ≤ t_i ≤ k, a_i ≤ b_i)$。

接下来 $q$行，每行包含两个整数 $l_i$和 $y_i$ ，表示一组（坐标，时间）查询$(1 ≤ l_i, y_i ≤ 10^8)$。

输出格式

输出一行，包含 $q$个整数，依次表示对于 $q$组（坐标，时间）询问求出的结果。

样例 #1

样例输入 #1

4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

样例输出 #1

4
2
-1
-1

样例 #2

样例输入 #2

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

样例输出 #2

0
0
-1

样例 #3

样例输入 #3

1 1 1
100000000 1 1 1
1 1

样例输出 #3

99999999

提示

提示

在第一个样例中，有 4 家商店，共 2 种类型，还有 4 个询问。

• 对于第一个询问：小明在第 3 年住在坐标为 5 的地方。这一年中，编号为 1 和 2 的商店在营业，到编号为 1 的商店的距离为 2 ，到编号为 2 的商店距离为 4 ，所以最大距离为$4$。
• 对于第二个询问：小明在第 6 年住在坐标为 5 的地方。这一年中，编号为 1 和 3 的商店在营业，到编号为 1 的商店的距离为 2 ，到编号为 3 的商店距离为 2 ，所以最大距离为$2$。
• 对于第三个询问：小明在第 9 年住在坐标为 5 的地方。这一年中，编号为 1 和 4 的商店在营业，它们的类型都为 1，没有类型为 2 的商店在营业，所以答案为 $-1$。
• 同样的情况出现在第四个询问中。

在第二个样例中，有 2 家商店，共 1 种类型，还有三个询问。 两家商店的类型都是 1 。在所有的询问中，小明均住在坐标为 1 的地方。 在前两个询问中，至少有一个商店在营业，所以答案为 $0$ ，在第三个询问中，两个商店都不在营业，所以答案为 $-1$ 。

在第三个样例中，有 1 家商店和 1 个询问，两者之间的距离是 $99999999$ 。

子任务（注：这里给出的子任务与本题在这里的最终评测无关，仅供参考）

• Subtask 1(points: $5$): $n, q \leq 400$
• Subtask 2(points: $7$): $n, q \leq 6 × 10^4, k \leq 400$
• Subtask 3(points: $10$): $n, q \leq 3 × 10^5$，对于所有的商店 $a_i = 1, b_i = 10^8$
• Subtask 4(points: $23$): $n, q \leq 3 × 10^5$，对于所有的商店 $a_i = 1$
• Subtask 5(points: $35$): $n, q \leq 6 × 10^4$
• Subtask 6(points: $20$): $n, q \leq 3 × 10^5$