题目描述

Stuart the Snail 住在一片田野上，这片田野可以被描述为一个无限的二维平面。在田野的每个整数坐标点上都有可以吃的植物，而 Stuart 的家位于原点 $(0, 0)$。

下雨了，Stuart 能够轻松地在田野上移动。每小时他可以选择一个相邻的植物坐标移动过去并吃掉它。具体来说，如果他当前在 $(x, y)$，他可以移动到 $(x+1, y)$、$(x, y+1)$、$(x-1, y)$ 或 $(x, y-1)$。他可以在雨停前继续移动，也可以选择停止并停留在某个植物上，包括留在原地。

然而，田野中有 $n$ 个深水坑，每个水坑覆盖一个矩形区域，Stuart 无法安全地通过。水坑 $i$ 的覆盖范围是满足 $a_i \leq x \leq b_i$ 且 $c_i \leq y \leq d_i$ 的所有整数坐标点。注意，水坑可能存在重叠。

你需要回答 $q$ 个查询，每个查询的类型由 $t$ 指定：

• 如果 $t = 1$，查询 Stuart 从原点移动到 $(x_j, y_j)$ 所需的最短时间（以小时为单位）。如果无法到达目的地，输出 $-1$。
• 如果 $t = 2$，假设雨将持续 $m_j$ 小时，计算 Stuart 在最多 $m_j$ 小时内可以到达的不同位置数量。

输入格式

• 第一行包含三个整数 $n$、$t$ 和 $q$，分别表示水坑数量、查询类型和查询数量。
• 接下来的 $n$ 行中，每行包含四个整数 $a_i$、$b_i$、$c_i$ 和 $d_i$，表示水坑 $i$ 的范围。
• 如果 $t = 1$，接下来的 $q$ 行每行包含两个整数 $x_j$ 和 $y_j$，表示查询的目标坐标。
• 如果 $t = 2$，接下来的 $q$ 行每行包含一个整数 $m_j$，表示雨的持续时间。

输出格式

• 对于每个查询，输出一个整数作为答案：
  • 如果 $t = 1$，输出 Stuart 到达目标位置的最短时间；如果无法到达，输出 $-1$。
  • 如果 $t = 2$，输出 Stuart 在最多 $m_j$ 小时内可以到达的不同位置数量。

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

3
8
-1
-1

2 1 4
-1000000000 -1 0 999999999
0 999999999 -1000000000 -1
1 1
-1 1
-1 -1
1 -1

2
-1
4000000002
-1

2 2 6
-2 5 1 1
0 1 -3 -2
1
2
3
4
5
6

4
8
13
21
32
48

2 2 4
0 9999999 -10000000 -1
-10000000 -1 10000000 29999999
12
1234
123456
12345678

235
2285986
22862261089
231374765559370

提示

【样例解释】

对于样例 #1：

• Stuart 可以在 $3$ 小时内到达 $(3, 3)$。
• Stuart 无法到达 $(2, -3)$，因为目标位置被水坑覆盖。

对于样例 #2：

• Stuart 在 $1$ 小时内可以到达 $4$ 个不同的位置。
• 在 $2$ 小时内，可以到达 $8$ 个位置。

【数据范围】

• $1 \leq n \leq 400$
• $1 \leq t \leq 2$
• $1 \leq q \leq 200,000$
• $-10^9 \leq a_i \leq b_i \leq 10^9$
• $-10^9 \leq c_i \leq d_i \leq 10^9$
• 原点 $(0, 0)$ 不被任何水坑覆盖。
• 如果 $t = 1$，则 $-10^9 \leq x_j, y_j \leq 10^9$。
• 如果 $t = 2$，则 $1 \leq m_j \leq 10^9$。