Фестиваль кавунів#253
У селі щороку влаштовують веселий фестиваль кавунів. Фермери з усієї округи привозять свої кавуни на конкурс, щоб визначити найбільший та найважчий кавун сезону. Цього року організатор фестивалю Олександр вирішив зробити подію ще цікавішою — він запровадив спеціальну послугу для туристів: фотографія з кавуном-чемпіоном дня!
Оскільки кавуни на фестивалі продовжують рости протягом усього свята, Олександру потрібно щодня визначати, який кавун є найважчим саме цього дня. На початку фестивалю він виміряв початкову вагу кожного кавуна та швидкість його росту. Тепер для будь-якого -го дня фестивалю він може обчислити вагу кожного кавуна за формулою W_K = W_0 + S \cdot K, де W_0 — початкова вага, а — швидкість росту цього кавуна.
Олександр надто зайнятий організацією фестивалю, щоб щодня робити ці обчислення вручну, тому він просить вас допомогти. Напишіть програму, яка визначить найважчий кавун у задані дні.
У першому рядку вхідного файлу міститься одне ціле число — кількість кавунів на фестивалі (1 \leq N \leq 10^5). Кожен з наступних рядків містить по два цілих числа W_0 та (1 \leq W_0, S \leq 10^9), розділених пропуском, — початкова вага та швидкість росту відповідного кавуна.
У наступному рядку міститься одне число — кількість днів, для яких потрібно знайти найважчий кавун (1 \leq M \leq 10^5). Кожен із останніх рядків містить по одному додатному цілому числу — номер дня (1 \leq K \leq 10^9), для якого потрібно дати відповідь.
У вихідний файл виведіть рядків — по одному для кожного дня у тому ж порядку, як і у вхідних даних. У відповідному рядку виведіть одне число — номер найважчого кавуна у цей день. Якщо таких кавунів кілька, виведіть мінімальний номер серед них. Кавуни нумеруються від до у порядку подання у вхідних даних.
Приклад 1