我们在老式计算机上使用画图程序。画图程序的屏幕是一个由称为像素的方格组成的网格。我们将最左下角像素的坐标设为 $(1, 1)$，向右第 $a$ 个、向上第 $b$ 个像素的坐标设为 $(a, b)$。初始屏幕上绘制了 $N$ 个具有垂直和水平边的矩形。矩形由该区域内包含的像素表示。

将对这 $N$ 个矩形执行 $M$ 次移动指令。矩形的移动方向包括东、西、南、北 4 个方向，以及东北、西北、东南、西南（与水平轴成 45 度角）4 个方向。此外，还会给出移动距离 $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)$（图 1）。

图 1

屏幕上矩形 $R$ 移动距离 $d$ 的过程，是通过依次快速显示 $R$ 从初始位置开始每移动距离 1 时的形态来实现的。然而，由于我们的计算机非常老旧，在 $R$ 移动时会出现严重的延迟。结果，在 $R$ 移动过程中绘制的所有 $R$ 的形态都会留在屏幕上。因此，当 $R$ 移动距离 $d$ 时，屏幕上会新产生 $d$ 个矩形。例如，在下方的图 2 中，如果矩形向东北方向移动距离 3，则会产生 3 个矩形，屏幕上总共留下 4 个矩形。当然，移动后，位于东北方向末端的矩形即为 $R$。

图 2

在执行 $M$ 次移动指令后，将给出 $Q$ 个询问。每个询问由平面上的一个像素 $p$ 给出。作为对询问的回答，输出包含像素 $p$ 的矩形个数。

实现细节

你需要实现以下函数：

vector<long long int> count_enclosing_rectangle(vector< pair<int, int> > R1, vector< pair<int, int> > R2, vector<int> V, vector<int> I, vector<int> D, vector< pair<int, int> > P )

• 该函数仅被调用一次。
• 作为参数给出的数组 R1 和 R2 的大小为 $N$。数组的每个元素代表初始给定的 $N$ 个矩形之一，R1[i] 和 R2[i] 是表示矩形 $i+1$ 的最左下角像素和最右上角像素坐标的有序对。如果有序对给定为 $(a, b)$，则坐标位置为 $(a, b)$。这里，矩形用 1 到 $N$ 的整数表示。
• 作为参数给出的数组 V、I 和 D 的大小为 $M$。数组的每个元素代表 $M$ 次矩形移动中的一次，表示矩形 I[i] 向 V[i] 方向移动了距离 D[i]。
• 作为参数给出的数组 P 的大小为 $Q$。数组的每个元素是询问对应的平面上像素 $p$ 的坐标有序对。如果有序对给定为 $(a, b)$，则坐标位置为 $(a, b)$。
• 该函数必须找出包含每个询问像素 $p$ 的矩形个数，并将其存入一个长度为 $Q$ 的数组中返回。第 $i$ 个值应该是第 $i$ 次询问的结果（$0 \le i \le Q-1$）。

在提交的源代码的任何部分都不得执行输入输出函数。

数据范围

• $1 \le N \le 250,000$
• $0 \le M \le 250,000$
• $1 \le Q \le 250,000$
• $1 \le R1[i].first \le R2[i].first \le 250,000$
• $1 \le R1[i].second \le R2[i].second \le 250,000$
• $0 \le V[i] \le 7$
• $1 \le I[i] \le N$
• $1 \le D[i] \le 250,000$
• 屏幕坐标值在 1 到 250,000 之间。任意矩形包含的所有像素的坐标值始终在此范围内。移动发生后此条件依然满足。询问给出的像素也满足此条件。
• 矩形移动方向 V[i] 的值为 0（东）、1（东北）、2（北）、3（西北）、4（西）、5（西南）、6（南）、7（东南）。

子任务

1. (8分) $N \le 100, M = 0$
2. (8分) $M = 0$
3. (11分) $M \le 100$
4. (13分) $V[i] \in \{0, 2, 4, 6\}$ ($0 \le i \le M-1$)。即矩形仅在上下左右方向移动。
5. (12分) $R1[i] = R2[i]$ ($0 \le i \le N-1$)
6. (48分) 无额外限制。

样例

输入格式 1

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

输出格式 1

4
5
3
2

说明

在上述示例中，3 个矩形的 3 次移动总共产生了 7 个矩形。因此，最终留下了 10 个矩形。像素 $(3, 3)$ 被矩形 1 产生的 2 个矩形和矩形 2 产生的 2 个矩形包含，总共被 4 个矩形包含。注意，这里矩形 1 移动产生的第三个矩形和矩形 2 虽然包含相同的区域，但被视为不同的矩形。count_enclosing_rectangle 函数结束时应返回数组 $[4, 5, 3, 2]$。