你在使用一台旧 Windows 电脑上的画图软件。画图软件的屏幕是一个由像素组成的网格。左下角像素的坐标为 $(1, 1)$，位于从左往右第 $a$ 列、从下往上第 $b$ 行的像素坐标为 $(a, b)$。在初始屏幕上，绘制了 $N$ 个边与坐标轴平行的矩形。一个左下角像素为 $(x_1, y_1)$、右上角像素为 $(x_2, y_2)$ 的矩形包含所有满足 $x_1 \le x \le x_2$ 且 $y_1 \le y \le y_2$ 的像素 $(x, y)$。

总共将对 $N$ 个矩形执行 $M$ 条移动指令。矩形的移动由方向和距离表示。每个方向为以下之一：东、西、南、北、东北、西北、东南和西南（后四个方向与水平轴成 45 度角）。每个距离 $d$ 都是一个正整数。

假设矩形左下角像素的初始坐标为 $(a, b)$。向东、北、西、南方向移动距离 $d$ 会使该像素分别向坐标 $(a + d, b)$、$(a, b + d)$、$(a - d, b)$ 和 $(a, b - d)$ 移动。此外，向东北、西北、西南和东南方向移动距离 $d$ 会使该像素分别向坐标 $(a + d, b + d)$、$(a - d, b + d)$、$(a - d, b - d)$ 和 $(a + d, b - d)$ 移动。

屏幕上矩形 $R$ 的距离为 $d$ 的移动是通过在 $R$ 每移动距离 1 时快速显示 $R$ 的形状来实现的。然而，我们的电脑非常老旧，所以移动 $R$ 会产生严重的延迟。结果，在 $R$ 移动过程中绘制的所有 $R$ 都留在了屏幕上。因此，如果 $R$ 移动了距离 $d$，屏幕上会新创建 $d$ 个矩形。例如，如果矩形向东北方向移动了距离 3，则会创建 3 个矩形，屏幕上总共留下 4 个矩形。当然，移动结束后，位于东北端的矩形即为 $R$。

执行 $M$ 条移动指令后，将给出 $Q$ 个查询。每个查询由平面上的一个像素 $p$ 给出。请输出包含像素 $p$ 的矩形数量作为查询的答案。

输入格式

第一行包含三个整数 $N, M$ 和 $Q$ ($1 \le N \le 250\,000, 0 \le M \le 250\,000, 1 \le Q \le 250\,000$)。

接下来的 $N$ 行，每行包含四个整数 $x_1, y_1, x_2$ 和 $y_2$，表示一个左下角像素为 $(x_1, y_1)$、右上角像素为 $(x_2, y_2)$ 的矩形 ($1 \le x_1 \le x_2 \le 250\,000, 1 \le y_1 \le y_2 \le 250\,000$)。

接下来的 $M$ 行，每行包含三个整数 $v_i, x_i$ 和 $d_i$，表示第 $x_i$ 个矩形沿方向 $v_i$ 移动了距离 $d_i$ ($0 \le v_i \le 7, 1 \le x_i \le N, 1 \le d_i \le 250\,000$)。

方向定义如下： 0: $(+1, 0)$ 1: $(+1, +1)$ 2: $(0, +1)$ 3: $(-1, +1)$ 4: $(-1, 0)$ 5: $(-1, -1)$ 6: $(0, -1)$ 7: $(+1, -1)$

接下来的 $Q$ 行，每行包含两个整数 $x$ 和 $y$，表示对像素 $(x, y)$ 的查询。

所有坐标均为 1 到 250\,000 之间的正整数。任何时刻包含在矩形中的像素均满足这些约束。查询的像素也满足这些约束。

输出格式

对于每个查询的像素，输出一个整数，表示包含该像素的矩形数量。

样例

样例输入 1

1 8 3
2 1 2 1
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
1 1
2 1
4 2

样例输出 1

0
2
1

样例输入 2

2 0 3
3 3 7 7
4 4 6 6
5 5
3 7
8 8

样例输出 2

2
1
0