E. Dictator's plan for Valentine's day!
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It's Valentine's Day. $$$N$$$ students decided to go for a movie with their partners. But wait! there is a problem, The $$$Dictator$$$ has allotted $$$M$$$ Guards on the way from $$$Ruby$$$ to $$$Main Gate$$$.

Consider the $$$RedCarpet$$$ which is full of $$$Roses$$$ placed from $$$Ruby$$$ to $$$Main Gate$$$ as positive-half of the number line starting with $$$Ruby$$$ at point $$$X$$$ = $$$0$$$ and $$$Main Gate$$$ is at $$$X$$$ = $$$\infty$$$. The $$$i^{th}$$$ Guard has been allotted his duty at the point $$$X_i$$$ during the time interval [$$$L_i-z$$$, $$$R_i-z$$$] where $$$z$$$ is your Luckiness factor [0<$$$z$$$<0.1] and the time starts at $$$t=0$$$.

Now the $$$i^{th}$$$ couple will starting walking at time $$$t$$$ = $$$T_i$$$ from $$$Ruby$$$ towards $$$Main Gate$$$ at speed $$$1$$$ $$$unit/sec$$$. They will not stop until they reach the Main Gate or are caught by any of the guards.

Input

All values in input are integers in the following format –

The first line contains two integers $$$M$$$, $$$N$$$ - the number of $$$Guards$$$ and number of $$$couple$$$.

Each of the following $$$M$$$ lines contains three integers $$$L_i$$$, $$$R_i$$$, $$$X_i$$$($$$1 \leq i\leq M$$$).

Each of next following $$$N$$$ lines contains $$$T_i$$$($$$1 \leq i\leq N$$$).

Input Constraints

$$$1\leq M, N \leq 2 \cdot 10^5$$$

$$$0\leq L_i < R_i \leq 10^9$$$

$$$1 \leq X_i \leq 10^9$$$

$$$0 \leq T_1 < T_2 < ... < T_N \leq 10^9$$$

If $$$i \neq j$$$ and $$$X_i = X_j$$$, the intervals [$$$L_i$$$,$$$R_i$$$) and [$$$L_j$$$,$$$R_j$$$) do not overlap.

Output

Print $$$N$$$ lines. If the $$$i^{th}$$$ $$$couple$$$ will be caught by any of the guards, then print the distance covered by them. Otherwise, they will go for the movie, so print $$$-1$$$.

Example
Input
4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8
Output
2
2
10
-1
13
-1
Note

The first couple starts coordinate 0 at time 0 and stop walking at coordinate 2 when reaching a point blocked by the first Guard at time 2.

The second couple starts coordinate 0 at time 1 and reach coordinate 2 at time 3. The first Guard has ended, but the fourth Guard has begun, so this couple also stop walking at coordinate 2.

The fourth and sixth couple encounter no Guard while walking, so they can go for the movie. The output for these cases is $$$-1$$$.