Read problems statements [Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

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

The restaurant is open during $N$ time intervals $[L_{1}, R_{1}), [L_{2}, R_{2}), \dots, [L_{N}, R_{N})$. No two of these intervals overlap — formally, for each valid $i$, $j$ such that $i \neq j$, either $R_{i} < L_{j}$ or $R_{j} < L_{i}$.

$M$ people (numbered $1$ through $M$) are planning to eat at the restaurant; let's denote the time when the $i$-th person arrives by $P_{i}$. 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 $0$ time), or determine that they will wait forever for the restaurant to open.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of the input contains two space-separated integers $N$ and $M$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $L_{i}$ and $R_{i}$.
$M$ lines follow. For each valid $i$, the $i$-th of these lines contains a single integer $P_{i}$.

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

------ Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N, M ≤ 10^{5}$
$1 ≤ L_{i} < R_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ P_{i} ≤ 10^{9}$ for each valid $i$
the intervals are pairwise disjoint
the sum of $N$ for all test cases does not exceed $3 \cdot 10^{5}$
the sum of $M$ for all test cases does not exceed $3 \cdot 10^{5}$

------ Subtasks ------
Subtask #1 (30 points):
the sum of $N$ for all test cases does not exceed $1,000$
the sum of $M$ for all test cases does not exceed $1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------
1
4 5
5 7
9 10
2 3
20 30
5
6
7
35
1
----- Sample Output 1 ------
0
0
2
-1
1
----- explanation 1 ------
Query $1$: The person coming at time $5$ does not have to wait as the restaurant is open in $[5,7)$ slot.

Query $2$: The person coming at time $6$ does not have to wait as the restaurant is open in $[5,7)$ slot.

Query $3$: The person coming at time $7$ has to wait since the restaurant is closed at time $7$. The next slot in which the restaurant opens is $[9,10)$. Thus, the person waits for $2$ units of time.

Query $4$: The person coming at time $35$ has to wait forever as the restaurant does not open after time $30$.

见题面

见题面