#214776. [ICPC 2025 Seoul R] Segments

In the first quadrant of a coordinate plane, you are given line segments parallel to the -axis. Each segment () is represented by the coordinates of its left and right endpoints, and , respectively. All coordinates are positive integers.

You must now answer queries. For each query, a vertical line , parallel to the -axis, is given. The vertical line is represented by a single positive integer .

If each segment is horizontally extended, it will eventually meet the line at the point . If the segment, including its endpoints, already meets , no extension is needed. For example, suppose there are 5 segments , , , , and , and a single line . The first segment must be extended by 6 to the right, the second segment 2 to the right, the third and the fourth segments 0, and the fifth segment 3 to the left for each to meet .

For each query, determine the maximum among the extension lengths required for all segments to meet the line . Formally, let denote the distance that segment must be extended to intersect at . For each query, output . In the example above, the answer to the query is 6. See the figure below.

:::align{center} :::

Given segments and 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 () and (), where is the number of line segments and is the number of queries. In the following lines, the -th line contains three integers, , , and (, ), where (resp. ) is the -coordinate of left (resp. right) endpoint of and is the -coordinate of both endpoints of . In the following lines of queries, the -th line contains one integer () which denotes the vertical line .

Your program is to write to standard output. Print exactly one line per each query. The -th line should contain the maximum among the extension lengths required for all segments to meet at .

样例输入 1

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

样例输出 1

6
9
13

样例输入 2

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

样例输出 2

9
5
8
4
9
7
11
12