蜗牛 Stuart 生活在一片田野上。这片田野可以描述为一个无限平面（二维空间）。田野上每一个坐标为整数的点都长有可食用的植物。Stuart 的家位于原点。
由于正在下雨，Stuart 可以轻松地四处移动。在一小时内，他可以选择当前位置相邻的四个可食用植物中的一个，移动到那里并吃点零食。形式化地说，如果他位于坐标 $(x, y)$，他可以移动到 $(x + 1, y)$、$(x, y + 1)$、$(x - 1, y)$ 或 $(x, y - 1)$。只要还在下雨，他就可以继续他的旅程，但也可以随时选择在任何长有可食用植物的位置停下来，包括直接待在家里。
然而，已知田野上有 $n$ 个深水坑。每个水坑覆盖一个矩形区域，且太深了，Stuart 无法安全通过。水坑 $i$ 阻止 Stuart 进入任何满足 $a[i] \le x \le b[i]$ 且 $c[i] \le y \le d[i]$ 的整数坐标 $(x, y)$。水坑可能会重叠。
目前尚不清楚雨会持续多久。请回答 $q$ 个由 $t$ 定义的同类型查询。
- 如果 $t = 1$，Stuart 想要访问坐标为 $(x[j], y[j])$ 的植物。假设雨永远不会停，求他到达 $(x[j], y[j])$ 所需的最短时间（以小时为单位）。如果他无法到达目的地，则输出 $-1$。
- 如果 $t = 2$，假设雨将持续 $m[j]$ 小时。计算 Stuart 在最多 $m[j]$ 小时后可以结束旅程的不同位置的数量。
输入格式
程序必须从标准输入读取数据。
第一行包含三个整数 $n$、$t$ 和 $q$，分别表示水坑的数量、查询类型和查询次数。
接下来的 $n$ 行，每行包含四个整数 $a[i]$、$b[i]$、$c[i]$ 和 $d[i]$，描述一个水坑。
如果 $t = 1$，接下来的 $q$ 行，每行包含两个整数 $x[j]$ 和 $y[j]$，描述一个目的地。
否则，如果 $t = 2$，接下来的 $q$ 行，每行包含一个整数 $m[j]$，描述一次查询中雨持续的时间。
输出格式
程序必须输出到标准输出。
对于每个查询，在单独的一行上输出一个整数作为答案。
子任务
对于所有测试用例，输入满足以下范围：
- $1 \le n \le 400$
- $1 \le t \le 2$
- $1 \le q \le 200\,000$
- $-10^9 \le a[i] \le b[i] \le 10^9$
- $-10^9 \le c[i] \le d[i] \le 10^9$
- $(0, 0)$ 不被任何水坑覆盖。
- 如果 $t = 1$，则 $-10^9 \le x[j], y[j] \le 10^9$
- 如果 $t = 2$，则 $1 \le m[j] \le 10^9$
你的程序将在满足以下限制的输入实例上进行测试：
| 子任务 | 分值 | 查询类型 $t$ | 附加限制 |
|---|---|---|---|
| 0 | 0 | 样例测试用例 | |
| 1 | 5 | $t = 1$ | $n \le 100$, $-400 \le a[i] \le b[i] \le 400$, $-400 \le c[i] \le d[i] \le 400$, $-400 \le x[j], y[j] \le 400$ |
| 2 | 17 | $t = 1$ | $n \le 100$, $a[i] \equiv c[i] \equiv 0 \pmod{10^7}$, $b[i] \equiv d[i] \equiv -1 \pmod{10^7}$ |
| 3 | 8 | $t = 1$ | $n \le 100$ |
| 4 | 8 | $t = 2$ | $n \le 100, q \le 400$, $-400 \le a[i] \le b[i] \le 400$, $-400 \le c[i] \le d[i] \le 400$, $m[j] \le 400$ |
| 5 | 21 | $t = 2$ | $n \le 100, q \le 400$, $a[i] \equiv c[i] \equiv 0 \pmod{10^7}$, $b[i] \equiv d[i] \equiv -1 \pmod{10^7}$ |
| 6 | 10 | $t = 2$ | $n \le 100, q \le 400$ |
| 7 | 13 | $t = 2$ | $n \le 100, q \le 5000$ |
| 8 | 14 | $t = 2$ | $n \le 100$ |
| 9 | 4 | $t = 2$ | 无附加限制 |
样例
样例输入 1
5 1 4 -4 -3 -2 5 -6 4 4 4 1 2 0 6 4 4 -1 4 -2 6 -4 -2 -1 2 3 3 0 6 2 -3
样例输出 1
3 8 -1 -1
说明 1
下图描述了原点周围的区域。蓝色矩形代表无法进入或通过的水坑。
如果不进入水坑，则无法到达最后两个目的地。注意，最后一个目的地被一个水坑覆盖。
样例输入 2
2 1 4 -1000000000 -1 0 999999999 0 999999999 -1000000000 -1 1 1 -1 1 -1 -1 1 -1
样例输出 2
2 -1 4000000002 -1
样例输入 3
2 2 6 -2 5 1 1 0 1 -3 -2 1 2 3 4 5 6
样例输出 3
4 8 13 21 32 48
样例输入 4
2 2 4 0 9999999 -10000000 -1 -10000000 -1 10000000 29999999 12 1234 123456 12345678
样例输出 4
235 2285986 22862261089 231374765559370