2D Paper Play

Bob plays with colored paper and blocks on a two-dimensional grid plane. Every block is 1x1, and several blocks can be stacked on the same cell. Suppose there are $N$ blocks, and let the position of the $i$-th block be $(x_i, y_i)$. In this problem the top-left cell is (1, 1), and the x axis runs left to right. In the top-left layout of the figure below, block 1 is at (2, 2) and block 3 is at (4, 3).

Bob also has $M$ sheets of paper. The $j$-th sheet is $w_j$ cells wide and $h_j$ cells tall. Paper cannot be rotated.

• The top-right layout places one 4 x 4 sheet covering (1, 1) through (4, 4). Blocks 1 and 3 fit entirely on this sheet.
• The bottom-left layout places one 8 x 4 sheet, and it holds 4 blocks.
• The bottom-right layout places one 9 x 3 sheet, and it holds 3 blocks.

Place the $j$-th sheet so that it covers the cells from (1, 1) to $(w_j, h_j)$. If $x_i \le w_j$ and $y_i \le h_j$, then the $j$-th sheet “includes” the $i$-th block. For each $i$, let $C_i$ be the number of sheets among the $M$ sheets that include block $i$, so $0 \le C_i \le M$.

Alice asks $Q$ questions. The $k$-th question gives two integers $L_k$ and $U_k$. Find the number of indices $i$ that satisfy $L_k \le C_i \le U_k$.

For example, with $N = 5$, $x = [2, 4, 8, 7, 3]$, $y = [2, 3, 3, 4, 5]$, $M = 3$, $w = [4, 8, 9]$, and $h = [4, 4, 3]$, the values are $C_1 = 3$, $C_2 = 2$, $C_3 = 3$, $C_4 = 1$, and $C_5 = 0$.

The first line contains the number of test cases $T$.

The first line of each test case contains $N$, $M$, and $Q$, separated by spaces. The next $N$ lines each contain $x_i$ and $y_i$. The next $M$ lines each contain $w_j$ and $h_j$. The next $Q$ lines each contain $L_k$ and $U_k$.

For each test case, print the answers to the $Q$ questions on one line, separated by spaces.