P16491 [GKS 2014 #D] GBus count

There exist some cities that are built along a straight road. The cities are numbered $1$, $2$, $3$... from left to right. There are $N$ GBuses that operate along this road. For each GBus, we know the range of cities that it serves: the i-th gBus serves the cities with numbers between $A_i$ and $B_i$, inclusive. We are interested in a particular subset of $P$ cities. For each of those cities, we need to find out how many GBuses serve that particular city.

The first line of the input gives the number of test cases, $T$. Then, $T$ test cases follow; each case is separated from the next by one blank line. (Notice that this is unusual for Kickstart data sets.) In each test case: * The first line contains one integer $N$: the number of GBuses. * The second line contains $2N$ integers representing the ranges of cities that the buses serve, in the form $A_1 \ B_1 \ A_2 \ B_2 \ A_3 \ B_3 \dots A_N \ B_N$. That is, the first GBus serves the cities numbered from $A_1$ to $B_1$ (inclusive), and so on. * The third line contains one integer $P$: the number of cities we are interested in, as described above. (Note that this is not necessarily the same as the total number of cities in the problem, which is not given.) * Finally, there are $P$ more lines; the i-th of these contains the number $C_i$ of a city we are interested in.

For each test case, output one line containing Case #x: y, where $x$ is the number of the test case (starting from $1$), and $y$ is a list of $P$ integers, in which the i-th integer is the number of GBuses that serve city $C_i$.

In Sample Case #1, there are four GBuses. The first serves cities $15$ through $25$, the second serves cities $30$ through $35$, the third serves cities $45$ through $50$, and the fourth serves cities $10$ through $20$. City $15$ is served by the first and fourth buses, so the first number in our answer list is $2$. City $25$ is served by only the first bus, so the second number in our answer list is $1$. ### Limits $1 \le T \le 10$. **Small dataset (Test Set 1 - Visible)** $1 \le N \le 50$ $1 \le A_i \le 500$, for all $i$. $1 \le B_i \le 500$, for all $i$. $1 \le C_i \le 500$, for all $i$. $1 \le P \le 50$. **Large dataset (Test Set 2 - Hidden)** $1 \le N \le 500$. $1 \le A_i \le 5000$, for all $i$. $1 \le B_i \le 5000$, for all $i$. $1 \le C_i \le 5000$, for all $i$. $1 \le P \le 500$.