题目描述

五福街可视为数轴，存在 $n$个商店，每个商店用 $(x_i, t_i, a_i, b_i)$描述：坐标$x_i$、类型 $t_i$、开业年份 $a_i$、关闭年份 $b_i$。

小明有 $q$ 个查询，每个查询为 $(l_i, y_i)$，表示在年份 $y_i$ 居住于坐标 $l_i$。定义“不方便指数”如下：

• 若某年份 $y$ 中，$k$ 种类型的商店均至少有一家营业（$a_i \leq y \leq b_i$），则不方便指数为所有类型中“最近营业商店到居住点的距离”的最大值。
• 若存在至少一种类型无营业商店，则不方便指数为 $-1$。

类型 $t$ 的最近距离定义：该类型所有营业商店中，到居住点 $l$ 的最小距离（$|x - l|$）。

输入格式

第一行包含三个整数$n, k, q$，分别表示商店数、类型数、查询数（$1 \leq n, q \leq 3 \times 10^5$，$1 \leq k \leq n$）。

接下来 $n$ 行，每行四个整数 $x_i, t_i, a_i, b_i$（$1 \leq x_i, a_i, b_i \leq 10^9$，$1 \leq t_i \leq k$，$a_i \leq b_i$）。

接下来 $q$ 行，每行两个整数 $l_i, y_i$（$1 \leq l_i, y_i \leq 10^8$）。

输出格式

输出 $q$ 个整数，依次为每个查询的不方便指数。

样例

样例 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  

输出：

4  
2  
-1  
-1  

说明：

• 第 1 个查询（5, 3）：类型 1 有商店 1（距离 2），类型 2 有商店 2（距离 4），最大值为 4。
• 第 3 个查询（5, 9）：类型 2 无营业商店，故为 -1。

样例 2
输入：

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

输出：

0  
0  
-1  

样例 3
输入：

1 1 1  
100000000 1 1 1  
1 1  

输出：

99999999  

数据范围与提示