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 ti, momentul de timp la care este detectată de radar, exprimat în ore, și vi, viteza acesteia, exprimată în km/h.

Cerința

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 ti, respectiv vi cu semnificația de mai sus (pentru orice i = 1..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 ≤ N ≤ 100.000
• 1 ≤ Q ≤ 300.000
• -1.000.000.000 ≤ vi , ti ≤ 1.000.000.000, vi ≠ 0 pentru orice i = 1..N
• -1.000.000.000 ≤ t ≤ 1.000.000.000 pentru orice interogare
• pentru teste în valoare de 32 de puncte 1 ≤ N ≤ 1000 și 1 ≤ Q ≤ 3000.

Exemplu:

Intrare

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

Ieșire

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.