There is an infinitely long street that runs west to east, which we consider as a number line.

There are N roadworks scheduled on this street. The i-th roadwork blocks the point at coordinate X_i from time S_i - 0.5 to time T_i - 0.5.

Q people are standing at coordinate 0. The i-th person will start the coordinate 0 at time D_i, continue to walk with speed 1 in the positive direction and stop walking when reaching a blocked point.

Find the distance each of the Q people will walk.

Constraints

* All values in input are integers.
* 1 \leq N, Q \leq 2 \times 10^5
* 0 \leq S_i < T_i \leq 10^9
* 1 \leq X_i \leq 10^9
* 0 \leq D_1 < D_2 < ... < D_Q \leq 10^9
* If i \neq j and X_i = X_j, the intervals [S_i, T_i) and [S_j, T_j) do not overlap.

Input

Input is given from Standard Input in the following format:


N Q
S_1 T_1 X_1
:
S_N T_N X_N
D_1
:
D_Q


Output

Print Q lines. The i-th line should contain the distance the i-th person will walk or -1 if that person walks forever.

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
import java.io.*;
import java.util.*;

class Main {

	public static void main(String[] args) throws Exception {
		final Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int Q = sc.nextInt();
		long[][] STX = new long[N][3];
		for (int i = 0; i < N; i++) {
			STX[i][0] = sc.nextLong();
			STX[i][1] = sc.nextLong();
			STX[i][2] = sc.nextLong();
			STX[i][0] -= STX[i][2];
			STX[i][1] -= STX[i][2];
		}
		Arrays.sort(STX, (a, b) -> Long.compare(a[2], b[2]));

		NavigableSet<long[]> s = new TreeSet<>((a, b) -> Long.compare(a[0], b[0]));
		for (int i = 0; i < Q; i++) {
			long d = sc.nextLong();
			s.add(new long[]{d, i});
		}

		long[] answer = new long[Q];
		Arrays.fill(answer, Long.MAX_VALUE);

		for (int i = 0; i < N; i++) {
			long[] stx = STX[i];
			while (true) {
				if (s.isEmpty()) break;
				long[] x = s.ceiling(new long[]{stx[0], 0});
				if (x == null) break;
				if (x[0] >= stx[1]) break;
				answer[(int) x[1]] = stx[2];
				s.remove(x);
			}
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < Q; i++) {
			if (answer[i] == Long.MAX_VALUE) {
				sb.append(-1);
			} else {
				sb.append(answer[i]);
			}
			sb.append("\n");
		}

		System.out.print(sb.toString());
	}


}
