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.*;


public class Main {
    static long mod = 1000000000+7;
    static int maxn=2;
    static long[] f5ac, inv;
    static ArrayList<Integer>[] rec;
    static int[] v;
    static int n,q;
    public static void main(String[] args) throws Exception {
        //Scanner sc = new Scanner(System.in);
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] buf = reader.readLine().split(" ");
        n = Integer.parseInt(buf[0]); q = Integer.parseInt(buf[1]);
        TreeMap<Integer,Integer> valIdx = new TreeMap<>();
        int[] D = new int[q];
        block[] rec = new block[n];
        for(int i=0;i<n;i++){
            buf = reader.readLine().split(" ");
            int s = Integer.parseInt(buf[0]), t = Integer.parseInt(buf[1]), x = Integer.parseInt(buf[2]);
            rec[i] = new block(s,t,x);
        }
        for(int i=0;i<q;i++){
            buf = reader.readLine().split(" ");
            D[i] = Integer.parseInt(buf[0]);
            valIdx.put(D[i],i);
        }
        Arrays.sort(rec,(a,b)->(a.x-b.x)); // let the ones with smaller x come first
        // check for every block
        int inf = Integer.MAX_VALUE/2;
        int[] res = new int[q];
        Arrays.fill(res,inf);
        for(int i=0;i<n;i++){
            block cur = rec[i];
            Integer left = valIdx.ceilingKey(cur.s-cur.x);
            Integer right = valIdx.lowerKey(cur.t-cur.x);
            if(left==null||right==null||left>right) continue; // no person affected
            int riBound = right;
            while(left!=null&&left<=riBound){
                int pos = valIdx.get(left);
                res[pos] = cur.x;
                valIdx.remove(left);
                left = valIdx.ceilingKey(cur.s-cur.x);
            }
        }
        PrintWriter out = new PrintWriter(System.out);
        for(int i=0;i<q;i++){
            if(res[i]==inf) out.println(-1);
            else out.println(res[i]);
        }
        out.flush();
    }
    static class block{
        int s, t, x;
        public block(int st, int te, int pos){
            this.s = st; this.t = te; this.x = pos;
        }
    }
}

