Festival Decorating

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

You will be given $q$ queries. In the $i$-th query, you are given an integer $d_i$ ($1 \le d_i \le 250000$). Find the lamp $u$ ($1 \le u \le n$) with the minimum index such that another lamp is located at $x_u + d_i$ and its color differs from $c_u$. If no such $u$ exists, the answer is impossible to find.

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 250000$). Each of the next $n$ lines contains $x_i$ and $c_i$ ($1 \le x_i \le 250000$, $1 \le c_i \le n$). Each of the next $q$ lines contains one integer $d_i$.

For each query, print one line containing the minimum index $u$. If no such $u$ exists, print $0$. An answer is correct if its absolute or relative error does not exceed $0.5$. That is, for your answer $u$ and the jury's answer $u'$, the answer is accepted when $\frac{|u - u'|}{\max(1, |u'|)} \le 0.5$. You may print a non-integer.