축제 장식

겨울 축제를 맞아 비트랜드의 중앙 대로를 장식하려고 한다. 이 대로는 $x$축으로 볼 수 있으며, 여기에 $n$개의 색깔 전구가 $1, 2, \ldots, n$번으로 번호가 매겨져 있다. $i$번 전구의 x좌표는 $x_i$이고 색은 $c_i$이다. 두 전구가 같은 x좌표를 갖는 경우는 없다.

$q$개의 질의가 주어진다. $i$번째 질의에서는 정수 $d_i$ ($1 \le d_i \le 250000$)가 주어진다. $x_u + d_i$ 위치에 다른 전구가 있고, 그 전구의 색이 $c_u$와 다른 전구 $u$ ($1 \le u \le n$) 중에서 번호가 가장 작은 것을 찾는다. 그런 $u$가 없을 수도 있다.

첫 줄에 두 정수 $n$과 $q$가 주어진다 ($1 \le n, q \le 250000$). 다음 $n$개 줄에는 각각 $x_i$와 $c_i$가 주어진다 ($1 \le x_i \le 250000$, $1 \le c_i \le n$). 다음 $q$개 줄에는 각각 정수 $d_i$가 하나씩 주어진다.

각 질의에 대해 답 $u$를 한 줄에 출력한다. 조건을 만족하는 $u$가 없으면 0을 출력한다. 답은 절대 오차 또는 상대 오차가 0.5 이하이면 정답으로 인정한다. 즉, 출력값 $u$와 정답 $u'$에 대해 $\frac{|u - u'|}{\max(1, |u'|)} \le 0.5$이면 정답이다. 소수를 출력해도 된다.