五福街是一条笔直的街道，可以看作一条一维数轴，街道上每栋建筑物的位置都可以用一个数字表示。时间旅行者小明知道，街上已经、正在或将要开设 $n$ 家商店，共有 $k$ 种商店类型。第 $i$ 家商店可以用四个整数 $x_i, t_i, a_i, b_i$ 来描述，分别表示商店的位置、商店类型、开业年份和结业年份。

时间旅行者小明想要选择五福街上的某一年和某个位置居住。他将自己的偏好缩小到了 $q$ 个“位置-年份”对。第 $i$ 个对可以用两个整数 $l_i, y_i$ 来描述，分别表示该对的位置和年份。现在他想评估这些对的生活质量。他将一个“位置-年份”对的“不便指数”定义为该对中最难到达的商店类型的不可达性。对于某种商店类型 $t$，其不可达性定义为从该位置到该年份营业的最近的 $t$ 类型商店的距离。我们称第 $i$ 家商店在 $y$ 年营业，如果 $a_i \le y \le b_i$。注意，在某些年份，五福街上可能没有全部 $k$ 种类型的商店。在这种情况下，不便指数定义为 $-1$。

你的任务是帮助小明找出每个“位置-年份”对的不便指数。

输入格式

第一行包含三个整数 $n, k, q$：商店数量、商店类型数量和查询数量 ($1 \le n, q \le 3 \cdot 10^5, 1 \le k \le n$)。

接下来 $n$ 行，每行包含四个整数 $x_i, t_i, a_i, b_i$，描述一家商店 ($1 \le x_i, a_i, b_i \le 10^8, 1 \le t_i \le k, a_i \le b_i$)。

接下来 $q$ 行，每行包含两个整数 $l_i, y_i$，描述一个查询 ($1 \le l_i, y_i \le 10^8$)。

输出格式

输出 $q$ 个整数：对于每个查询，输出其不便指数。

子任务

子任务 1（5 分）： $n, q \le 400$

子任务 2（7 分）： $n, q \le 6 \cdot 10^4, k \le 400$

子任务 3（10 分）： $n, q \le 3 \cdot 10^5, a_i = 1, b_i = 10^8$（对所有商店）

子任务 4（23 分）： $n, q \le 3 \cdot 10^5, a_i = 1$（对所有商店）

子任务 5（35 分）： $n, q \le 6 \cdot 10^4$

子任务 6（20 分）： $n, q \le 3 \cdot 10^5$

样例

样例输入 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 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

样例输出 2

0
0
-1

样例输入 3

1 1 1
100000000 1 1 1
1 1

样例输出 3

99999999

说明

在第一个样例中，有四家商店、两种类型和四个查询。

• 第一个查询：小明住在位置 5，年份为 3。在这一年，商店 1 和 2 营业，到商店 1 的距离为 2，到商店 2 的距离为 4。最大值为 4。
• 第二个查询：小明住在位置 5，年份为 6。在这一年，商店 1 和 3 营业，到商店 1 的距离为 2，到商店 3 的距离为 2。最大值为 2。
• 第三个查询：小明住在位置 5，年份为 9。在这一年，商店 1 和 4 营业，它们都是类型 1，因此没有类型 2 的商店，不便指数为 $-1$。
• 第四个查询情况相同。

在第二个样例中，有两家商店、一种类型和三个查询。两家商店的位置都在 1，所有查询中小明都住在位置 1。前两个查询中至少有一家商店营业，因此答案为 0；第三个查询中两家商店都已结业，因此答案为 $-1$。

在第三个样例中，有一家商店和一个查询。位置之间的距离为 99999999。