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
```
