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.util.Arrays;
        import java.util.TreeSet;

public class Main{
    private static void solve() {
        int n = ni();
        int q = ni();
        int[][] p = new int[n][4];

        for (int i = 0; i < n; i++) {
            int s = ni();
            int t = ni();
            int x = ni();
            p[i][0] = s - x;
            p[i][1] = t - x;
            p[i][2] = x;
            p[i][3] = i;
        }
        Arrays.sort(p, (o1, o2) -> o1[0] - o2[0]);

        TreeSet<int[]> q1 =
                new TreeSet<>((o1, o2) -> o1[1] == o2[1] ? o1[3] - o2[3] : o1[1] - o2[1]);
        TreeSet<int[]> q2 =
                new TreeSet<>((o1, o2) -> o1[2] == o2[2] ? o1[3] - o2[3] : o1[2] - o2[2]);

        int ptr = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            int d = ni();

            while (ptr < n && p[ptr][0] <= d) {
                q1.add(p[ptr]);
                q2.add(p[ptr]);
                ptr++;
            }

            while (q1.size() > 0 && q1.first()[1] <= d) {
                int[] v = q1.pollFirst();
                q2.remove(v);
            }

            if (q2.size() > 0) {
                sb.append(q2.first()[2]);
            } else {
                sb.append(-1);
            }
            sb.append("\n");
        }
        System.out.println(sb);

    }

    public static void main(String[] args) {

        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();

//        new Thread(null, new Runnable() {
//            @Override
//            public void run() {
//                long start = System.currentTimeMillis();
//                String debug = args.length > 0 ? args[0] : null;
//                if (debug != null) {
//                    try {
//                        is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
//                    } catch (Exception e) {
//                        throw new RuntimeException(e);
//                    }
//                }
//                reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
//                solve();
//                out.flush();
//                tr((System.currentTimeMillis() - start) + "ms");
//            }
//        }, "", 64000000).start();
    }

    private static java.io.InputStream is = System.in;
    private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
    private static java.util.StringTokenizer tokenizer = null;
    private static java.io.BufferedReader reader;

    public static String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new java.util.StringTokenizer(reader.readLine());
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    private static double nd() {
        return Double.parseDouble(next());
    }

    private static long nl() {
        return Long.parseLong(next());
    }

    private static int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = ni();
        return a;
    }

    private static char[] ns() {
        return next().toCharArray();
    }

    private static long[] nal(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nl();
        return a;
    }

    private static int[][] ntable(int n, int m) {
        int[][] table = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                table[i][j] = ni();
            }
        }
        return table;
    }

    private static int[][] nlist(int n, int m) {
        int[][] table = new int[m][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                table[j][i] = ni();
            }
        }
        return table;
    }

    private static int ni() {
        return Integer.parseInt(next());
    }

    private static void tr(Object... o) {
        if (is != System.in)
            System.out.println(java.util.Arrays.deepToString(o));
    }
}
