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 S_i metri de originea axei. De asemenea, se ştie că fiecare concurent i se deplasează cu o viteză constantă V_i, 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 S_i şi viteza V_i. 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 10⁹.
• 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).

prof. Marius Nicoli

Colegiul Naţional „Fraţii Buzeşti” Craiova

mariusnicoli@yahoo.com