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 p_{i} will lie in a segment A B if A ≤ p_{i} ≤ 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 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 A_{k} B_{k} (0 ≤ A_{k} ≤ B_{k} ≤ 10^{8}) denoting a segment.
Each of the next q lines contains an integer denoting a point. Each of them range in [0, 10^{8}].
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 |
Dataset is huge, use faster I/O methods.
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |