406959: GYM102625 E Dictator's plan for Valentine's day!
Description
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.
InputAll 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.
OutputPrint $$$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$$$.
ExampleInput4 6 1 3 2 7 13 10 18 20 13 3 4 2 0 1 2 3 5 8Output
2 2 10 -1 13 -1Note
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$$$.