radar

Pe axa numerelor reale, considerăm o autostradă cu un număr nelimitat de benzi. În dreptul bornei corespunzătoare kilometrului $0$ (originea axei numerelor reale) se află un radar. Acest radar depistează $N$ mașini care circulă cu viteze constante. Pentru fiecare mașină $i$ se cunosc $t_i$, momentul de timp la care este detectată de radar, exprimat în ore, și $v_i$, viteza acesteia, exprimată în km/h.

Cerință

Să se răspundă la $Q$ interogări de forma: dându-se $t$, care este la momentul $t$ cea mai apropiată mașină de radar dintre cele detectate până atunci (inclusiv cele detectate fix la momentul $t$)? Dacă există mai multe mașini dintre cele detectate până la momentul $t$ pentru care distanța față de radar este minimă, puteți afișa oricare dintre ele.

Date de intrare

Prima linie conține numerele $N$ și $Q$, numărul de mașini, respectiv numărul de interogări. Urmează $N$ linii, pe a $i$-a dintre acestea se citesc doua numere $t_i$, respectiv $v_i$ cu semnificația de mai sus (pentru orice $i = 1 \dots N$). Ultima linie conține $Q$ numere întregi, corespunzând celor $Q$ interogări (pentru fiecare interogare se citește un număr corespunzător lui $t$ cu semnificația de mai sus).

Date de ieșire

Se va afișa o singură linie ce va conține $Q$ numere separate prin câte un spațiu, corespunzând răspunsurilor la interogări. Pentru fiecare interogare $t$ se afișează indicele celei mai apropiate mașini față de radar la momentul $t$, dintre cele detectate până la momentul $t$ (mașinile sunt indexate începând de la $1$ în ordinea în care au fost citite). Dacă până la momentul $t$ nu s-a detectat nicio mașină se va afișa $-1$ pentru interogarea respectivă.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq Q \leq 300 \ 000$
• $-1 \ 000 \ 000 \ 000 \leq v_i , t_i ≤ 1 \ 000 \ 000 \ 000$, $v_i \neq 0$ pentru orice $i = 1 \dots N$
• $-1 \ 000 \ 000 \ 000 \leq t \leq 1 \ 000 \ 000 \ 000$ pentru orice interogare
• Pentru teste în valoare de $32$ de puncte $1 \leq N \leq 1 \ 000$ și $1 \leq Q \leq 3 \ 000$.

Exemplu

stdin

3 3
2 1
4 2
-2 -1
1 3 4

stdout

3 1 2

Explicație

La momentul $t = 1$ doar cea de a treia mașină fusese deja detectată.
La momentul $t = 3$, radarul detectase deja mașinile $1$ și $3$, dintre acestea cea mai apropiată de radar la momentul $t = 3$ este mașina $1$, aflată la distanță $1$.
La momentul $t = 4$, radarul detectase deja toate mașinile. Dintre acestea, cea mai apropiată este mașina $2$, aflată la distanța $0$ de radar.