시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 1024 MB 5 4 4 100.000%

문제

You are using Paint on an old computer. The screen of Paint is a grid with cells called pixels. Let the coordinates of the lower-left pixel be $(1, 1)$, and the coordinates of the $a$th pixel from the left and the $b$th pixel from the bottom are $(a, b)$. On the initial screen, $N$ rectangles with vertical and horizontal sides are drawn. A rectangle is represented by pixels contained within this area.

$M$ move commands will be performed on $N$ rectangles. The movement of the rectangle are represented by the pair of direction and distance. The directions are one of the following: east, west, south, north, northeast, northwest, southeast, and southwest (45 degrees to the horizontal axis). The distance is a positive integer $d$. Suppose that the original coordinates of the pixels of the leftmost and bottom corners of the rectangle are $(a, b)$. the movement by a distance of $d$ in the east, north, west, and south directions causes the rectangle to move toward the coordinate $(a+d, b)$, $(a, b+d)$, $(a-d, b)$, $(a, b-d)$. In addition, the movement by a distance of $d$ in the northeast, northwest, southwest, and southeast directions causes the rectangle to move toward the coordinate $(a+d, b+d)$, $(a-d, b+d)$, $(a-d, b-d)$, $(a+d, b-d)$ 

Moving by distance $d$ of the rectangle $R$ on the screen is implemented by quickly displaying the shapes of $R$ every time when $R$ moves by distance 1. However, our computer is very old, so moving $R$ is very laggy. As a result, all of the $R$ drawn in the movement of $R$ remains on the screen. Therefore, if $R$ moves by the distance $d$, $d$ rectangles are newly created on the screen. For example, if the rectangle moves in the northeast direction by a distance of 3, 3 rectangles are created, leaving a total of 4 rectangles on the screen. Of course, after moving, the rectangle at the northeast end becomes $R$.

After executing $M$ move commands, $Q$ queries will be given. Each query is given as a pixel $p$ on the plane. Print the number of rectangles containing the pixel $p$ as an answer to the query.

입력

The first line contains three space-separated integers $N, M, Q$.

The next $N$ lines contain four space-separated integers $x_1, y_1, x_2, y_2$, denoting a rectangle with lowest-leftmost pixel $(x_1, y_1)$ and highest-rightmost pixel $(x_2, y_2)$.

The next $M$ lines contain three space-separated integers $v_i, x_i, d_i$, denoting that the $x_i$-th rectangle moved toward the direction $v_i$ by distance $d_i$. The directions are:

  • 0: $(+1, 0)$
  • 1: $(+1, +1)$ 
  • 2: $(0, +1)$
  • 3: $(-1, +1)$ 
  • 4: $(-1, 0)$
  • 5: $(-1, -1)$ 
  • 6: $(0, -1)$
  • 7: $(+1, -1)$ 

The next $Q$ lines contain two space-separated integers $x, y$, denoting the query on pixel $(x, y)$.

출력

For each query, print the single integer denoting the number of rectangles containing the given pixel.

제한

  • $1 \le N \le 250,000$
  • $0 \le M \le 250,000$
  • $1 \le Q \le 250,000$
  • $1 \le x_1 \le x_2 \le 250,000$
  • $1 \le y_1 \le y_2 \le 250,000$
  • $0 \le v_i \le 7$
  • $1 \le x_i \le N$
  • $1 \le d_i \le 250,000$
  • All coordinates are a positive integer from $1$ to $250\,000$. Any pixels contained in a rectangle at any time satisfies this constraints. Queried pixels also satisfies this constraints.

서브태스크

번호 배점 제한
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

$x_1 = x_2, y_1 = y_2$

6 48

No additional limits.

예제 입력 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

출처

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.