그림판 렉

오래된 컴퓨터에서 그림판을 사용하고 있다. 그림판 화면은 픽셀이라 부르는 칸으로 이루어진 격자이다. 가장 왼쪽 아래 픽셀의 좌표를 $(1, 1)$로 하고, 오른쪽으로 $a$번째, 위쪽으로 $b$번째에 있는 픽셀의 좌표를 $(a, b)$로 한다. 초기 화면에는 변이 수직, 수평인 직사각형 $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

직사각형 $R$을 거리 $d$만큼 이동할 때는 시작 위치를 포함해서 $R$이 거리 1만큼 움직일 때마다 그 순간의 $R$ 모습을 차례로 빠르게 그린다. 이 컴퓨터는 매우 오래되어 이동할 때 렉이 심하게 걸린다. 그 결과 이동 중에 그려진 $R$의 모습이 모두 화면에 그대로 남는다. 따라서 $R$이 거리 $d$만큼 이동하면 $d$개의 직사각형이 새로 화면에 만들어진다. 예를 들어 그림 2에서 직사각형이 북동 방향으로 거리 3만큼 이동하면 직사각형 3개가 새로 만들어져서 화면에는 총 4개의 직사각형이 남는다. 이동이 끝나면 북동쪽 끝에 있는 직사각형이 $R$이 된다.

그림 2

$M$개의 이동 명령을 수행한 뒤 $Q$개의 질의가 주어진다. 각 질의는 평면 위의 픽셀 $p$로 주어진다. 각 질의마다 픽셀 $p$를 포함하는 직사각형의 개수를 구한다.

첫째 줄에 공백으로 구분된 세 정수 $N$, $M$, $Q$가 주어진다.

다음 $N$개의 줄에는 공백으로 구분된 네 정수 $x_1$, $y_1$, $x_2$, $y_2$가 주어진다. 직사각형의 가장 왼쪽 아래 픽셀의 좌표가 $(x_1, y_1)$, 가장 오른쪽 위 픽셀의 좌표가 $(x_2, y_2)$라는 뜻이다. 직사각형은 1번부터 $N$번까지 주어진 순서대로 번호가 붙는다.

다음 $M$개의 줄에는 공백으로 구분된 세 정수 $v_i$, $x_i$, $d_i$가 주어진다. $x_i$번째 직사각형을 $v_i$ 방향으로 거리 $d_i$만큼 이동한다는 뜻이다. $v_i$의 값에 따른 방향은 다음과 같다.

• 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$가 주어진다. 질의에 해당하는 픽셀 $p$의 좌표이다.

각 질의마다 픽셀 $p$를 포함하는 직사각형의 개수를 한 줄에 하나씩, 질의 순서대로 출력한다.

• $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$
• 모든 픽셀의 좌표는 이동 후에도 1 이상 250,000 이하이다. 질의로 주어지는 픽셀도 이 조건을 만족한다.