Diffusing Blocks

You are given m piles of blocks. The i-th pile is initially located at coordinate \(x_i\) and contains \(c_i\) blocks.

You repeatedly perform the following operation until no more operations can be done:

• If there exists any coordinate that contains at least two blocks, then among all such coordinates, choose the one with the smallest value, say \(x\). Then among the blocks at position \(x\), select any two blocks and perform a split: move one block to \(x-1\) and the other to \(x+1\).

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

After the process ends, you will be given several queries. Each query gives you a positive integer \(k\) and asks: what is the position of the \(k\)-th block from the left (i.e. in increasing order of coordinates)? The queries are given with strictly increasing \(k\) values.

Note: In every splitting operation the sum of the coordinates of the two blocks remains unchanged (i.e. \(x-1 + x+1 = 2x\)).

inputFormat

The first line contains two integers \(m\) and \(q\) — the number of piles and the number of queries.

Each of the next \(m\) lines contains two integers \(x_i\) and \(c_i\) — the coordinate of the pile and the number of blocks in that pile.

Each of the next \(q\) lines contains a single integer \(k\), representing a query. The queries are given in strictly increasing order.

You may assume that the total number of blocks is at least as large as the largest \(k\) queried.

outputFormat

For each query, output a single line containing one integer — the coordinate of the \(k\)-th block from the left after the process has finished.

sample

1 1
0 3
1

-1