URI Online Judge | 1777

Walk of Fame

By Gustavo Stor, UFPE BR Brazil

Timelimit: 1

In Hollywood Walk of Fame, there are numerous stars on the sidewalk with the name of many famous artists. Some vandals, maybe because of jealousy or for just no reason at all, were defacing many of the stars and putting other names instead:

The City Mayor, trying to minimize this problem, installed many surveillance cameras over the sidewalk. The sidewalk can be seen as a segment [1..N], where each position can possibly contain a star.

Each camera protect a range [a..b], inclusive. The City Mayor now wants to know, for each star, if they are protected by a camera or not. You were hired to do this job.


The first line contains T (1 ≤ T ≤ 100), the number of test cases. Each test case begins with two integers N (1 ≤ N ≤ 10⁹) and C (1 ≤ C ≤ 10⁴), the length of the sidewalk and the number of installed cameras, respectively. Following there are C lines, each one describing the camera i with two integers ai and bi (1 ≤ aibiN), representing the range covered by the camera. The next line contains a number E (1 ≤ E ≤ 10⁴), the number of stars. Following, there is a line with E integers xi, indicating the position of the i-th star on the sidewalk (1 ≤ xi ≤ N).


For each test case print “Caso #X: Y”, where X is the number of the current case, beginning with 1, and Y is the number of stars that are protected by some camera.

Input Sample Output Sample

10 3
1 3
1 4
7 8
2 5 8
2 1
1 2
1 1 2

Caso #1: 2
Caso #2: 3