E. Treasures in the Interval
time limit per test
1 second
memory limit per test
125 megabytes
input
standard input
output
standard output

You are given an array $$$A$$$ of length $$$N$$$ (1-indexed). There are $$$Q$$$ operations, and the $$$i$$$-th operation is described by three integers $$$L$$$, $$$R$$$, $$$d$$$, meaning add the integer $$$d$$$ to every element $$$A[L], A[L+1], \dots, A[R]$$$. All $$$Q$$$ operations are applied to the array in the given order.

After all operations are applied, you must answer $$$M$$$ independent queries. Each query gives an integer $$$K$$$, and you should output the K-th largest value in the resulting array.

Input

The first line contains three integers $$$N, Q, M$$$ $$$(1 \le N \le 2\times 10^5, \, 1 \le Q \le 2\times 10^5, \, 1 \le M \le 2\times 10^5)$$$ — the array length, the number of range updates, and the number of queries.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$\lvert A_i \rvert \le 10^9$$$ for all $$$i$$$) — the initial array.

Each of the next $$$Q$$$ lines contains three integers $$$L, R, d$$$ $$$(1 \le L \le R \le N, \, -10^6 \le d \le 10^6)$$$ describing a range addition.

The next line contains $$$M$$$ integers $$$K_1, K_2, \ldots, K_M$$$ $$$(1 \le K_i \le N)$$$ — the queries.

All integers are separated by single spaces.

Output

Print $$$M$$$ lines. On the $$$i$$$-th line, output a single integer — the $$$K_i$$$-th largest element of the array after all updates.

Example
Input
5 3 3
1 2 3 4 5
1 3 10
2 5 -4
5 5 100
1 2 5
Output
101
11
0