문제
오래된 컴퓨터에서 그림판을 사용하고 있다. 그림판의 화면은 픽셀이라 부르는 칸을 가진 격자 모양이다. 가장 왼쪽 아래 픽셀의 좌표를 (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)가 된다.
화면에서 직사각형 R의 거리 d만큼 이동은 초기 위치를 포함해서 R이 거리 1 만큼 이동할 때마다 R의 모습을 순서대로 빠르게 나타냄으로서 구현된다. 하지만 우리의 컴퓨터는 아주 오래 되어서 R의 이동 시 렉이 심하게 걸린다. 결과적으로 R의 이동에서 그리게 되는 모든 R의 모습이 화면에 그대로 남아있게 된다. 따라서 R이 거리 d만큼 이동하면, d개의 직사각형들이 새롭게 화면에 만들어진다. 예를 들어, 직사각형이 북동방향으로 거리 3만큼 이동하면, 3개의 직사각형들이 만들어져서 총 4개의 직사각형이 화면 위에 남게 된다. 물론, 이동 후에는 북동 방향 끝에 있는 직사각형이 R 이 된다.
M개의 이동 명령을 수행한 후 Q개의 질의가 주어질 것이다. 각 질의는 평면 상의 픽셀 p로 주어진다. 질의에 대한 대답으로 픽셀 p를 포함하는 직사각형들의 개수를 출력한다.
입력
첫 줄에 N, M, Q가 주어진다.
이후 N개의 줄에 X1[i], Y1[i], X2[i], Y2[i]가 주어진다.
이는 i번째 직사각형의 왼쪽 아래 픽셀이 (X1[i], Y1[i]), 오른쪽 위 픽셀이 (X2[i], Y2[i])임을 의미한다.
이후 M개의 줄에 V[i], I[i], D[i]가 주어진다.
이는 I[i]번 직사각형이 V[i] 방향으로 D[i]칸 이동한 것을 의미한다.
이후 Q개의 줄에 각 질의 픽셀의 좌표값이 주어진다.
• 1 ≤ N ≤ 250,000
• 0 ≤ M ≤ 250,000
• 1 ≤ Q ≤ 250,000
• 1 ≤ X1[i] ≤ X2[i] ≤ 250,000
• 1 ≤ Y1[i] ≤ Y2[i] ≤ 250,000
• 0 ≤ V[i] ≤ 7
• 1 ≤ I[i] ≤ N
• 1 ≤ D[i] ≤ 250,000
• 화면의 좌표 값은 1이상 250,000이하이다. 임의의 직사각형에 포함되는 모든 픽셀들의 좌표값이 항상 이 범위안에 있다. 이는 이동이 일어난 이후에도 만족한다. 쿼리로 주어지는 픽셀 역시 이 조건을 만족한다.
• 직사각형의 이동 방향 V[i]의 값은 0(동쪽), 1(북동), 2(북쪽), 3(북서), 4(서쪽), 5(서남), 6(남쪽), 7(남동) 이다.
출력
각 질의의 답을 한 줄에 하나씩 출력하라.
예제
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
4
5
3
2
로그인해야 코드를 작성할 수 있어요.