Server Time: Sat Sep 21, 2019 12:55 pm
Welcome ( logout
1089 - Points in Segments (II)
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 64 MB

Given n segments (1 dimensional) and q points, for each point you have to find the number of segments which contain that point. A point pi will lie in a segment A B if A ≤ pi ≤ B.

For example, if the segments are (6 12), (8 8), (10 12), (8 11), (0 12) and the point is 11, then it is contained by 4 segments.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing two integers n (1 ≤ n ≤ 50000) and q (1 ≤ q ≤ 50000).

Each of the next n lines contains two integers Ak Bk (0 ≤ Ak ≤ Bk ≤ 108) denoting a segment.

Each of the next q lines contains an integer denoting a point. Each of them range in [0, 108].

Output

For each case, print the case number in a single line. Then for each point, print the number of segments that contain that point.

Sample Input

Output for Sample Input

1

5 4

6 12

8 8

10 12

8 11

0 12

11

12

2

20

Case 1:

4

3

1

0

Notes

Dataset is huge, use faster I/O methods.


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan