Day by day number of Kangaroos is decreasing just like tiger, whale or lions. So I decided to make them a sanctuary where they will live peacefully. I do not let visitors go near them. So I planted some display screen outside the sanctuary. For this problem, you may assume the sanctuary to be a long line of 1000000000 unit distance. The leftmost position is marked with 0 and the rightmost position with 1000000000. There are at most 100000 cameras on this line. Each of the cameras is described with (L, R) which means that camera covers a range from position L to position R inclusive. Each of the cameras has their associated display screens outside where the visitors can see the Kangaroos. Now for the convenience of the spectators we announce time to time: “Kangaroo appears in Screen 3”, “Kangaroo appears in Screen 7” and so on. I have some employees who continuously monitor the position of Kangaroos and inform the system (here position is a marker). The system chooses the best screen to display that animal based on the coverage. The coverage of a screen for a position x is defined as follows: If the position x is outside the range of that screen (i.e. x < L or x > R) then the coverage is zero. Otherwise the coverage is min(x − L, R − x). An example will make it clear: Suppose there are four screens covering the range (7, 15), (14, 100), (8, 10) and (1, 11). Now say one Kangaroo appears at x = 10. First screen has coverage of 3 unit around x = 10. Because x = 10 is within (7, 15) and min(10 − 7, 15 − 10) = min(3, 5) = 3. Second screen has coverage of 0 unit around x = 10. Because x = 10 does not belong to the range (14, 100). Third screen has coverage of 0 unit around x = 10. Because though x = 10 is within (8, 10) but min(10 − 8, 10 − 10) = 0. Fourth screen has coverage of 1 unit around x = 10. Because x = 10 is within (1, 11) and min(10 − 1, 11 − 10) = 1. So which one is better? Obviously the first one, as it has the maximum coverage. So you are given the ranges of the screens and the positions the kangaroo appears. For each position of the Kangaroo you are to tell me the maximum coverage you can have with any of the screens. Input First line of the test file contains T (T ≤ 3), number of test cases. Hence T cases follow. For each case you are given N, M in the first line; N is the number of screens and M is the number of Kangaroo appearance (1 ≤ N,M ≤ 100000). In the next N lines you are given the range of screens L R (0 ≤ L ≤ R ≤ 1000000000). Next M lines contain the position of the Kangaroo — an integer x (0 ≤ x ≤ 1000000000).
2/2 Output For each case print the case number. Hence print M lines, i-th containing the maximum coverage you can have around i-th Kangaroo. Warning: The judge input file is around 6 MB. So use faster I/O functions. Sample Input 1 32 7 15 14 100 1 11 10 120 Sample Output Case 1: 3 0