Гарбузи Поля Чудес Країни Дурнів
Світова фінансова криза обвалила економіку Країни Дурнів, і Буратіно вирішив вирощувати гарбузи для отримання додаткового прибутку. Звичайно, він став використовувати для цього знамените Поле Чудес. Дякуючи його заповзятості (а моливо завдяки чудесних особливостям поля) швидкість росту гарбузів не змінювалась у часі, але могла бути різною для різних гарбузів. Гарбузи Поля Чудес стали знаменитими і привабливими для туристів.
Виявивши, що туристи люблять фотографуватись з гарбузами, Буратіно запустив новий сервіс для VIP туристів - фото з найважчим гарбузом.
Одного разу Буратіно одночасно виміряв вагу і швидкості росту для всіх гарбузів. Тепер для довільного K-го дня після дня вимірювань він може обчислити вагу довільного гарбуза за формулою W_K = W_0 + S*K, де W_0 - початкова вага, а S - швидкість росту для відповідного гарбуза.
Буратіно занадто лінивий для проведення всіх цих розрахунків щоденно і вручну, а тому просить вас допомогти йому. Напишіть програму, яка знайде найважчий гарбуз на заданий день.
Вхідні дані
Перший рядок вхідного файлу містить одне ціле число N - кількість гарбузів на полі (1 <= N <= 10^5). Кожен з наступних N рядків містить два цілих числа, відокремлених одиночним пропуском. W_0 и S (1 <= W_0, S <= 10^9) - початкові вага і швидкість росту для відповідного гарбуза.
Наступний рядок містить одне ціле число M - кіслькість днів, для яких ви повинні знайти самий важкий гарбуз (1 <= M <= 10^5). Кожен з наступних M рядків вхідного файлу містить одне ціле додатне число K (1 <= K <= 10^9) для якого ви повинні дати відповідь на питання задачі.
Вихідні дані
Вихідний файл повинен містити M рядків - по одному рядку для кожного дня у тому ж порядку, в якому дано питання у вхідному файлі. У відповідному рядку виведіть одне ціле число - номер найважчого гарбуза у відповідний день. Якщо таких гарбузів декілька, виведіть гарбуз з мінімальним номером серед них. Гарбузи нумеруються числами від 1 до N у тому порядку, в якому вони задані у вхідному файлі.