Chef Restaurant

Chef is a cook and he has recently opened a restaurant.

The restaurant is open during NN time intervals [L1,R1),[L2,R2),…,[LN,RN)[L1,R1),[L2,R2),…,[LN,RN). No two of these intervals overlap — formally, for each valid ii, jj such that i≠ji≠j, either Ri<LjRi<Lj or Rj<LiRj<Li.

MM people (numbered 11 through MM) are planning to eat at the restaurant; let's denote the time when the ii-th person arrives by PiPi. If the restaurant is open at that time, this person does not have to wait, but if it is closed, this person will wait until it is open. Note that if this person arrives at an exact time when the restaurant is closing, they have to wait for the next opening time.

For each person, calculate how long they have to wait (possibly 00 time), or determine that they will wait forever for the restaurant to open.

Input

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.

• The first line of the input contains two space-separated integers NN and MM.

• NN lines follow. For each valid ii, the ii-th of these lines contains two space-separated integers LiLi and RiRi.

• MM lines follow. For each valid ii, the ii-th of these lines contains a single integer PiPi.

Output

For each test case, print MM lines. For each valid ii, the ii-th of these lines should contain a single integer — the time person ii has to wait, or −1−1 if person ii has to wait forever.

Constraints

• 1≤T≤1001≤T≤100

• 1≤N,M≤1051≤N,M≤105

• 1≤Li<Ri≤1091≤Li<Ri≤109 for each valid ii

• 1≤Pi≤1091≤Pi≤109 for each valid ii

• the intervals are pairwise disjoint

• the sum of NN for all test cases does not exceed 3⋅1053⋅105

• the sum of MM for all test cases does not exceed 3⋅1053⋅105

Subtasks

Subtask #1 (30 points):

• the sum of NN for all test cases does not exceed 1,0001,000

• the sum of MM for all test cases does not exceed 1,0001,000

Subtask #2 (70 points): original constraints

Example Input

1
4 5
5 7
9 10
2 3
20 30
5
6
7
35
1

Example Output

0
0
2
-1
1

class Codechef {
    // O(NlogN) + O(MlogN)
    public static int[] waitingTime(int[][] intervals, int[] customers) {
        // Sorting on start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        // Now just binary searching for customers
        int[] ans = new int[customers.length];
        for (int i = 0; i < ans.length; i++)
            ans[i] = findTime(intervals, customers[i]);
        return ans;
    }

    public static int findTime(int[][] intervals, int arrival) {
        if (arrival >= intervals[intervals.length - 1][1])
            return -1;
        int low = 0, high = intervals.length - 1;
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arrival >= intervals[mid][0] && arrival < intervals[mid][1]) {
                ans = 0;
                break;
            } else if (arrival >= intervals[mid][1])
                low = mid + 1;
            else {
                // If the arrival time is just before this interval
                if (mid == low || intervals[mid - 1][1] <= arrival) {
                    ans = intervals[mid][0] - arrival;
                    break;
                }
                high = mid - 1;
            }
        }
        return ans;
    }
}