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개를 올린다.

$j$번째 색종이를 (1, 1)부터 $(w_j, h_j)$까지 덮도록 놓았을 때 $x_i \le w_j$이고 $y_i \le h_j$이면, $j$번째 색종이가 $i$번째 블록을 “포함한다”고 한다. 각 $i$에 대해 $C_i$는 $M$장의 색종이 중 $i$번째 블록을 포함하는 색종이의 수이며, 따라서 $0 \le C_i \le M$이다.

Alice는 $Q$개의 질문을 한다. $k$번째 질문은 정수 $L_k$, $U_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$, $C_2 = 2$, $C_3 = 3$, $C_4 = 1$, $C_5 = 0$이다.

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

각 테스트 케이스의 첫 줄에는 $N$, $M$, $Q$가 공백으로 구분되어 주어진다. 다음 $N$줄에는 $x_i$와 $y_i$, 다음 $M$줄에는 $w_j$와 $h_j$, 다음 $Q$줄에는 $L_k$와 $U_k$가 주어진다.

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