You cannot submit for this problem because the homework's deadline is due.

Input

The first line contains two integers P and H (0 ≤ P ≤ \(10^6\), 0 ≤ H ≤ \(10^6\)) – the number of webpages you should finish and the maxium number of homework that will not be caught HC.

The next n lines contain three integers each: s_i, t_i, h_i (0 ≤ \(s_i\) < \(t_i\) ≤ \(10^9\), 0 ≤ \(h_i\) ≤ \(10^6\)).
That is your should-start time, deadline and number of homework if your friend is to help you.

The next line contains single integer T (1 ≤ T ≤ \(10^7\)) – the number of computation.

Each of the computation is described with one integer t_i (1 ≤ \(t_i\) ≤ \(10^9\)) – the required number of minutes.

Output

For each computation task print one integer – the minimum minute you can complete it.

Submit Format

Submit a tar or zip file including a script named hc.py

Sample 1

Input

3 5
1 7 1
1 6 2
1 7 1
3
7
2
5

Output

12
7
10

Note

Consider this example. For all the three computation, it is optimal to give your friend webpage 1 and 3. Then the remaining wepage will occupy your computer on time segment [1,6]. So, intervals [0,1] and [6..\(\infty\)) are free.