Fiind un concurs mai special, “Cupa Şcolii la Atletism” are şi reguli speciale. Competiţia constă într-o probă de alergare la care participă N elevi, codificaţi cu numere naturale de la 1 la N. Aceştia pornesc în cursă în acelaşi timp, dar nu pleacă din acelaşi loc. Ne putem imagina că ei vor alerga de-a lungul axei Ox, în sens pozitiv şi că fiecare concurent i porneşte la momentul 0 din punctul aflat la Si metri de originea axei. De asemenea, se ştie că fiecare concurent i se deplasează cu o viteză constantă Vi, exprimată în metri pe secundă.
Cerinţă
Scrieţi un program care să răspundă la întrebări de tipul: "care dintre concurenţi este pe locul 1 după q de secunde?"
Date de intrare
Fişierul de intrare atletism.in conţine pe prima linie două numere naturale separate printr-un spaţiu N şi Q, reprezentând numărul de concurenţi, respectiv numărul de întrebări. Pe următoarele N linii se află câte două numere, separate prin câte un spaţiu, reprezentând în ordine, pentru fiecare concurent i (1≤i≤N) poziţia de start Si şi viteza Vi. Pe următoarele Q linii se află cele Q întrebări, câte o întrebare pe o linie. Pentru fiecare întrebare este specificat un număr natural reprezentând numărul de secunde pentru care trebuie determinat concurentul aflat pe primul loc în cursă.
Date de ieşire
Fişierul de ieşire atletism.out va conţine Q linii. Pe linia i va fi scris un singur număr, cuprins între 1 şi N, reprezentând răspunsul la întrebarea i. Întrebările sunt numerotate de la 1 la Q, în ordinea din fişierul de intrare.
Restricţii
1 ≤ N ≤ 500
1 ≤ Q ≤ 500000
1 ≤ Numărul de secunde specificat în întrebări ≤ 500000.
Pentru fiecare întrebare, distanţa parcursă de cel mai rapid concurent este un număr natural mai mic decât 109.
Poziţiile iniţiale ale concurenţilor sunt distincte (adică oricare două elemente din şirul S sunt distincte).
Dacă la un moment dat mai mulţi concurenţi sunt la egalitate pe prima poziţie, în fişierul de ieşire se va scrie concurentul cu codul minim.
Numerele ce reprezintă întrebările nu apar neapărat în ordine crescătoare şi se pot repeta.
Exemplu
atletism.in
atletism.out
Explicaţie
2 2
3 3
0 5
1
2
1
2
Iniţial concurentul 1 este înaintea concurentului 2. După prima secundă, concurentul 1 este pe primul loc (la 6 metri de origine, faţă de concurentul 2 care este la 5 metri). După 2 secunde concurentul 2 trece locul 1 (ajunge la 10 metri de origine, iar primul concurent este la 9 metri).