We are using a paint program on an old computer. The screen of the paint program is a grid of cells called pixels. The coordinates of the bottom-left pixel are $(1, 1)$, and the coordinates of the pixel at the $a$-th column from the left and $b$-th row from the bottom are $(a, b)$. Initially, $N$ rectangles with vertical and horizontal sides are drawn on the screen. A rectangle is represented by the set of pixels contained within its area.

$M$ movement commands will be performed on the $N$ rectangles. The movement of a rectangle occurs in one of 8 directions: East, West, South, North, and North-East, North-West, South-East, South-West (at a 45-degree angle to the horizontal axis). A movement distance $d$ is also given. In other words, a movement command is given by a direction and a distance. Specifically, if the coordinates of the bottom-left pixel of a rectangle are $(a, b)$, then a movement of distance $d$ in the East, North, West, or South direction results in the corner becoming $(a+d, b)$, $(a, b+d)$, $(a-d, b)$, and $(a, b-d)$, respectively. Furthermore, a movement of distance $d$ in the North-East, North-West, South-West, or South-East direction results in the corner becoming $(a+d, b+d)$, $(a-d, b+d)$, $(a-d, b-d)$, and $(a+d, b-d)$, respectively (Figure 1).

Figure 1

On the screen, the movement of a rectangle $R$ by distance $d$ is implemented by quickly displaying the appearance of $R$ in sequence for every distance of 1, including its initial position. However, our computer is very old, so there is significant lag when moving $R$. Consequently, all appearances of $R$ drawn during the movement remain on the screen. Therefore, when $R$ moves by distance $d$, $d$ new rectangles are created on the screen. For example, in Figure 2 below, if a rectangle moves in the North-East direction by a distance of 3, 3 new rectangles are created, leaving a total of 4 rectangles on the screen. Of course, after the movement, the rectangle at the North-East end becomes $R$.

Figure 2

After performing $M$ movement commands, $Q$ queries will be given. Each query is given as a pixel $p$ on the plane. As an answer to the query, output the number of rectangles that contain the pixel $p$.

Implementation Details

You must implement the following function:

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 )

• This function is called exactly once.
• The size of the input arrays R1 and R2 is $N$. Each element of the array represents one of the $N$ initially given rectangles, and R1[i] and R2[i] are ordered pairs representing the coordinates of the bottom-left pixel and the top-right pixel of rectangle $i+1$, respectively. If an ordered pair is given as $(a, b)$, the position of the coordinate is $(a, b)$. Here, rectangles are represented by integers from 1 to $N$.
• The size of the input arrays V, I, and D is $M$. Each element of the array represents one of the $M$ rectangle movements, indicating that rectangle I[i] moves in direction V[i] by distance D[i].
• The size of the input array P is $Q$. Each element of the array P is an ordered pair representing the coordinates of a pixel $p$ on the plane corresponding to the query. If an ordered pair is given as $(a, b)$, the position of the coordinate is $(a, b)$.
• This function must determine the number of rectangles containing the pixel $p$ for each query and return them in an array of length $Q$. The $i$-th value must be the result of the $i$-th query ($0 \le i \le Q - 1$).

You must not execute any input/output functions in any part of the submitted source code.

Constraints

• $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$
• The coordinate values on the screen are between 1 and 250,000. The coordinates of all pixels contained in any rectangle are always within this range. This is also satisfied after the movement occurs. The pixels given as queries also satisfy this condition.
• The value of the rectangle movement direction V[i] is 0 (East), 1 (North-East), 2 (North), 3 (North-West), 4 (West), 5 (South-West), 6 (South), 7 (South-East).

Subtasks

1. (8 points) $N \le 100, M = 0$
2. (8 points) $M = 0$
3. (11 points) $M \le 100$
4. (13 points) $V[i] \in \{0, 2, 4, 6\}$ ($0 \le i \le M - 1$). That is, the rectangles only move vertically or horizontally.
5. (12 points) $R1[i] = R2[i]$ ($0 \le i \le N - 1$)
6. (48 points) No additional constraints.

Sample Grader

The sample grader reads input in the following format:

• Line 1: $N \ M \ Q$
• Line $1 + i$ ($1 \le i \le N$): R1[i-1].first R1[i-1].second R2[i-1].first R2[i-1].second
• Line $1 + N + i$ ($1 \le i \le M$): V[i-1] I[i-1] D[i-1]
• Line $1 + N + M + i$ ($1 \le i \le Q$): P[i-1].first P[i-1].second

The sample grader outputs:

• Line $i$ ($1 \le i \le Q$): The $i$-th element of the array returned by the count_enclosing_rectangle function.

Note that the sample grader may differ from the actual grader used for evaluation.

Examples

Input 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

Output 1

4
5
3
2

Note

In this example, a total of 7 rectangles are created from 3 movements of 3 rectangles. Therefore, a total of 10 rectangles remain in the end. Pixel $(3, 3)$ is contained in 2 rectangles created by rectangle 1 and 2 rectangles created by rectangle 2, for a total of 4 rectangles. Note that here, the third rectangle of rectangle 1's movement and rectangle 2 are rectangles that contain the same area, but they are considered separate rectangles.