Арбузы Поля Чудес Страны Дураков
Мировой финансовый кризис обвалил экономику Страны Дураков, и Буратино решил выращивать арбузы для получения дополнительного дохода. Естественно, он стал использовать для этого знаменитое Поле Чудес. Из-за особого усердия (а может быть из-за чудесных особенностей поля) скорость роста арбузов не изменялась во времени, но могла быть разной для разных арбузов. Арбузы Поля Чудес стали знаменитыми и привлекательными для туристов.
Обнаружив, что туристы любят фотографироваться с арбузами, Буратино запустил новый сервис для 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 в том порядке, в котором они заданы во входном файле.