렉

오래된 컴퓨터에서 그림판을 사용하고 있다. 그림판의 화면은 픽셀이라 부르는 칸을 가진 격자 모양이다. 가장 왼쪽 아래 픽셀의 좌표를 $(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$의 모습이 화면에 그대로 남아있게 된다. 따라서 $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$의 정수로 나타내며, $1$번 직사각형부터 순서대로 주어진다.

다음 $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$의 좌표 $(x, y)$를 나타낸다.

각각의 질의마다 질의의 픽셀 $p$를 포함하는 직사각형들의 개수를 출력한다. $i$번째 줄에는 $i$번 질의의 결과를 출력해야 한다. ($0 ≤ i ≤ Q-1$)

• $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$이하이다. 임의의 직사각형에 포함되는 모든 픽셀들의 좌표값이 항상 이 범위안에 있다. 이는 이동이 일어난 이후에도 만족한다. 쿼리로 주어지는 픽셀 역시 이 조건을 만족한다.