Segments

문제

In the first quadrant of a coordinate plane, you are given $nn$ line segments parallel to the $xx$-axis. Each segment $S_{i}S\_i$ (1 ≤ i ≤ n) is represented by the coordinates of its left and right endpoints, $(l_i,y_i)(l\_i\; ,\; y\_i\; )$ and $(r_i,y_i)(r\_i\; ,\; y\_i\; )$, respectively. All coordinates are positive integers.

You must now answer $qq$ queries. For each query, a vertical line $x=px\; =\; p$, parallel to the $yy$-axis, is given. The vertical line is represented by a single positive integer $pp$.

If each segment $S_{i}S\_i$ is horizontally extended, it will eventually meet the line $x=px\; =\; p$ at the point $(p,y_i)(p,\; y\_i\; )$. If the segment, including its endpoints, already meets $x=px\; =\; p$, no extension is needed. For example, suppose there are $55$ segments $\{(2,3),(5,3)\}\backslash \{(2,\; 3),\; (5,\; 3)\backslash \}$, $\{(4,6),(9,6)\}\backslash \{(4,\; 6),\; (9,\; 6)\backslash \}$, $\{(8,2),(12,2)\}\backslash \{(8,\; 2),\; (12,\; 2)\backslash \}$, $\{(11,4),(13,4)\}\backslash \{(11,\; 4),\; (13,\; 4)\backslash \}$, and $\{(14,5),(17,5)\}\backslash \{(14,\; 5),\; (17,\; 5)\backslash \}$, and a single line $x=11x\; =\; 11$. The first segment must be extended by $66$ to the right, the second segment $22$ to the right, the third and the fourth segments $00$, and the fifth segment $33$ to the left for each to meet $x=11x\; =\; 11$.

For each query, determine the maximum among the extension lengths required for all segments to meet the line $x=px\; =\; p$. Formally, let $\text{dist}(p,S_i)\backslash text\{dist\}(p,\; S\_i\; )$ denote the distance that segment $S_{i}S\_i$ must be extended to intersect $x=px\; =\; p$ at $(p,y_i)(p,\; y\_i\; )$. For each query, output \max_{1≤i≤n}{\text{dist}(p, S_i )}. In the example above, the answer to the query is $66$. See the figure below.

Given $nn$ segments and $qq$ queries, write a program to output the maximum extension length for each query.

입력

Your program is to read from standard input. The input starts with a line containing two integers $nn$ (1 ≤ n ≤ 2 \times 10^6) and $qq$ (1 ≤ q ≤ 2 \times 10^6), where $nn$ is the number of line segments and $qq$ is the number of queries. In the following $nn$ lines, the $ii$-th line contains three integers, $l_{i}l\_i$, $r_{i}r\_i$, and $y_{i}y\_i$ (1 ≤ l_i ≤ r_i ≤ 10^9; 1 ≤ y_i ≤ 10^3), where $l_{i}l\_i$ (resp. $r_{i}r\_i$) is the $xx$-coordinate of left (resp. right) endpoint of $S_{i}S\_i$ and $y_{i}y\_i$ is the $yy$-coordinate of both endpoints of $S_{i}S\_i$. In the following $qq$ lines of queries, the $jj$-th line contains one integer $p_{j}p\_j$ (1 ≤ p_j ≤ 10^9) which denotes the vertical line $x=p_{j}x\; =\; p\_j$.

출력

Your program is to write to standard output. Print exactly one line per each query. The $jj$-th line should contain the maximum among the extension lengths required for all segments to meet $x=p_{j}x\; =\; p\_j$ at $(p_j,y_j)(p\_j\; ,\; y\_j)$.

5 3
2 5 3
4 9 6
8 12 2
11 13 4
14 17 5
11
5
1

6
9
13

4 8
1 4 7
3 7 5
10 13 8
12 15 2
13
7
4
8
3
11
1
16

9
5
8
4
9
7
11
12