33428번 - Festival Decorating 다국어

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$.

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.

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{.}$$