There are $n$ candy types. There are $a_i$ candies of type $i$ and they weigh $w_i$ each. No 2 types of candy have the same weight.

All the candies are poured onto a table and arranged in a row so that their weight form a non-decreasing list. You are given $q$ queries, how heavy is the $k^{th}$ candy on the table?

Input

• The first line contains 3 integers $n, q$.
• Next $n$ lines, each line contains 2 integers $a_i, w_i$.
• Next $q$ lines, each line contains a single integer $k$, a query.

Output

• Print $q$ lines, $i^{th}$ is the answer for query $i$.

Constraints

• $1 \le n, q \le 10^5$.
• $1 \le a_i, w_i \le 10^9$.
• $1 \le k \le a_1 + a_2 + … + a_n \le 10^{14}$.

Example

Input:

3 3
2 2
1 1
3 3
1
3
5

Output:

1
2
3