2차원 종이 놀이

Bob은 2차원 격자무늬 평면에 색종이와 블록을 올려놓고 재미있는 놀이를 하고 있다. 각 블록의 크기는 1x1로 모두 동일하며, 같은 위치에 블록을 여럿 쌓을 수도 있다. 조금 더 구체적으로, $N$개의 블록이 있을 때 $i$ 번째 블록의 위치는 $(x\_i, y\_i)$ 라 하자. 이 문제의 예제에서 좌측 상단이 (1, 1) 이며 좌-우가 $x$축이다. 가령 아래 그림에서 좌측 상단의 경우 1번 블록은 (2, 2) 위치에 있고 3번 블록은 (4, 3) 위치에 있다.

Bob은 또한 $M$ 장의 색종이를 갖고 있는데 $j$ 번째 색종이의 크기는 가로 $w\_j$ 칸 세로 $h\_j$ 칸 이며, 이 문제에서는 색종이를 회전하지 않는다고 하자.

• 위 그림에서 우측 상단의 경우 크기가 4 x 4인 색종이를 이용하여 (1, 1)부터 (4, 4)까지 완전히 덮은 경우를 보여 준다. 이 때, 1번 블록과 3번 블록은 이 색종이 위에 온전하게 놓을 수 있다.
• 좌측 하단의 경우 크기가 8 x 4인 색종이를 배치하면 총 4개의 블록을 그 위에 놓을 수 있다.
• 마지막으로, 우측 하단의 경우 크기가 9 x 3인 색종이를 배치하여 총 3개의 블록을 그 위에 놓은 모습을 볼 수 있다.

Bob이 블록과 색종이를 이용해 다양한 놀이를 하던 중, 이를 지켜보던 Alice는 동생 Bob에게 아래와 같은 문제를 풀어보라고 했다.

• 만약 $j$번째 색종이를 격자무늬 평면의 (1, 1)칸 부터 $(w\_j, h\_j)$ 칸 까지 덮도록 놓았을 때 $i$ 번째 블록이 그 색종이 위해 놓인다면 (즉, $x\_i \le w\_j$ 이고 $y\_i \le h\_j$ 라면), $j$ 번째 색종이가 $i$번째 블록을 "포함한다" 라고 정의하자.
• 각 $i$번째 블록에 대해 $C\_i$ 는 $M$장의 색종이 중 $i$ 번째 블록을 "포함하는" 색종이의 개수라 하자 -- 따라서 $0 \le C\_i \le M$ 이다.

이제, 위 정의를 이용하여 Alice는 Bob에게 총 $Q$ 개의 질문을 하는데, $k$ 번째 질문은 두 개의 정수 $L\_k, U\_k$ 로 표현된다:

• $k$번째 질문은: $L\_k \le C\_i \le U\_k$ 인 $i$의 개수가 무엇인가?

예를 들어 위 그림의 경우, $N = 5$ 이고 블록의 좌표는 $x = \[2, 4, 8, 7, 3]$ 과 $y = \[2, 3, 3, 4, 5]$ 로 표현할 수 있다. $M = 3$장의 색종이는 앞서 언급한 순서대로 크기가 $w = \[4, 8, 9]$ 그리고 $h = \[4, 4, 3]$ 이라 하자.

• $C\_1 = 3$ 이다: 세 장의 색종이 모두 1번 블록을 포함할 수 있다.
• $C\_2 = 2$ 이다: 2, 3번 색종이만 2번 블록을 포함할 수 있다.
• $C\_3 = 3$, $C\_4 = 1$, 그리고 $C\_5 = 0$ 이다.

만약 Alice가 총 $Q = 5$개의 질문을 하고, $L = \[0, 1, 0, 1, 2]$ 그리고 $U = \[2, 3, 3, 1, 3]$ 이라면 각 질문에 대한 답은 아래와 같다.

• $C$ 값이 0이상 2이하인 경우는 2, 4, 5번 블록에 해당하므로 첫 번째 질문의 답은 3이다.
• $C$ 값이 1이상 3이하인 경우는 1, 2, 3, 4번 블록에 해당하므로 두 번째 질문의 답은 4이다.
• 마찬가지로, 세 번째 질문의 답은 5, 네 번째 질문의 답은 1, 그리고 다섯 번째 질문의 답은 3이 된다.

입력으로 $N$개의 블록의 위치, $M$장의 색종이 크기, 그리고 Alice의 질문 $Q$개가 주어졌을 때, 각 질문에 대한 답을 구하여 Bob을 도와주자.

입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N, M, Q$ 가 공백으로 구분되어 주어진다. 다음 $N$줄은 각 블록의 위치를 나타내며 각 줄에 $x\_i$ 와 $y\_i$가 공백으로 구분되어 주어진다. 다음 $M$줄은 각 색종이의 크기를 나타내며 각 줄에 $w\_j$ 와 $h\_j$가 공백으로 구분되어 주어진다. 다음 $Q$줄은 Alice의 질문을 나타내며 각 줄에 $L\_k$ 와 $U\_k$가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 한 줄에 출력한다 -- 이 줄에는 $Q$개의 질문에 대한 답을 공백으로 구분하여 출력한다.