B. Festival Decorating
time limit per test
9 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

To celebrate the coming winter festival in Byteland, the main street, which can be regarded as the x-axis, is decorated with $$$n$$$ colorful lamps, labeled by $$$1, 2, \ldots, n$$$. The x-coordinate of the $$$i$$$-th lamp is $$$x_i$$$, and the color of the $$$i$$$-th lamp is $$$c_i$$$. No two lamps share the same x-coordinate.

You will be given $$$q$$$ queries. In the $$$i$$$-th query, you will be given an integer $$$d_i$$$ ($$$1 \leq d_i \leq 250\,000$$$), and you need to find the lamp $$$u$$$ ($$$1 \leq u \leq n$$$) with the minimum index such that there is another lamp located at $$$x_u + d_i$$$ and the color of that lamp is different from $$$c_u$$$, or determine it is impossible to find such $$$u$$$. Your answer is considered correct if its absolute or relative error does not exceed $$$0.5$$$.

Input

The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 250\,000$$$) denoting the number of lamps and the number of queries.

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$c_i$$$ ($$$1 \leq x_i \leq 250\,000$$$, $$$1 \leq c_i \leq n$$$) denoting the x-coordinate and the color of the $$$i$$$-th lamp. It is guaranteed that no two lamps share the same x-coordinate.

Each of the next $$$q$$$ lines contains a single integer $$$d_i$$$ ($$$1 \leq d_i \leq 250\,000$$$) denoting the $$$i$$$-th query.

Output

For each query, print a line containing a single number: the minimum index $$$u$$$ you found. If it is impossible to find such $$$u$$$, print $$$0$$$ instead.

Your answer is considered correct if its absolute or relative error does not exceed $$$0.5$$$. Note that this means you can output a non-integer as well.

Formally, let your answer be $$$u$$$, and the jury's answer be $$$u'$$$. Your answer is accepted if and only if: $$$$$$\frac{|u - u'|}{\max(1, |u'|)} \le 0.5\text{.}$$$$$$

Example
Input
4 5
3 1
1 2
5 1
6 2
1
2
3
4
5
Output
3
2
1
2
0