There are $m$ piles of blocks, where the $i$-th pile is located at coordinate $x_i$ and contains $c_i$ blocks.

Repeatedly perform the following operation until it is no longer possible:

• If there are two blocks at the same coordinate, find the two blocks with the smallest coordinate among those that satisfy the condition, decrease the coordinate of one by $1$, and increase the coordinate of the other by $1$.

It can be proven that after a finite number of operations, the coordinates of all blocks will be distinct, at which point no further operations can be performed.

Given multiple queries, each with a positive integer $k$, find the position of the $k$-th block from the left. It is guaranteed that the queries $k$ are strictly increasing.

Input

The input is read from standard input.

The first line contains a positive integer $m$. It is guaranteed that $1 \le m \le 2 \times 10^6$.

The next $m$ lines each contain two positive integers $x_i$ and $c_i$. It is guaranteed that $1 \le x_i \le 10^9$ and $1 \le c_i \le 10^9$. It is guaranteed that $x_i$ are strictly increasing in the order of input, i.e., $x_i < x_{i+1}$.

The next line contains a positive integer $q$, representing the number of queries. It is guaranteed that $1 \le q \le 2 \times 10^6$.

The next $q$ lines each contain a positive integer $k$, representing a query. It is guaranteed that $1 \le k \le \sum_{i=1}^{m} c_i \le 10^9$. It is guaranteed that the queries $k$ are strictly increasing.

Output

Output to standard output.

Output $q$ lines, each containing an integer, where the $i$-th line represents the answer to the $i$-th query.

Examples

Input 1

2
3 3
4 2
2
2
4

Output 1

2
5

Note 1

We describe the positions of the five blocks from left to right using a non-decreasing sequence of length 5. The operation process is as follows:

$33344 \to 23444 \to 23345 \to 22445 \to 13445 \to 13355 \to 12455 \to 12446 \to 12356$

Finally, the coordinate of the second block is 2, and the coordinate of the fourth block is 5.