GBus Count (Large)

Cities are built along a straight road. They are numbered 1, 2, 3, ... from left to right.

N GBuses run along this road. Each GBus has a fixed range of cities that it serves: the i-th GBus serves every city whose number is between Ai and Bi, inclusive.

You are given P cities of interest. For each of them, find how many GBuses serve it.

The first line contains the number of test cases, T. Then T test cases follow, and one blank line separates each test case from the next.

Each test case is given as follows.

• The first line contains one integer N, the number of GBuses.
• The second line contains 2N integers describing the ranges the buses serve, in the order A1 B1 A2 B2 A3 B3 ... AN BN. That is, the first GBus serves the cities numbered from A1 to B1.
• The third line contains one integer P, the number of cities of interest. This value need not equal the total number of cities on the road, and that total is never given.
• Each of the following P lines contains one integer. The i-th of them is the number Ci of a city of interest.

For each test case, print one line in the form Case #x: y, where x is the test case number starting from 1, and y is a list of P integers separated by single spaces. The i-th integer is the number of GBuses that serve city Ci.

• $1 \le T \le 10$
• $1 \le N \le 500$
• $1 \le A_i \le B_i \le 5000$
• $1 \le C_i \le 5000$
• $1 \le P \le 500$

In the first test case of the first example 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 the fourth bus, so the first number of the answer is 2. City 25 is served by the first bus only, so the second number is 1.