Мэд — фронтмен известной рок-группы. На последнем выступлении он разбил все свои гитары об ударную установку своего же барабанщика и теперь задумывается над покупкой новой гитары.

В магазине Галактической Федерации продаются N различных гитар, гитара номер i стоит Ki галактических долларов. Однако Мэд живет в Соединенном Королевстве Берляндии, поэтому в наличии у Мэда только бурли. Курс галактического доллара относительно бурля абсолютно непредсказуем и меняется каждый день, в день j он равен Xj бурлей за доллар. При этом курс может быть нулевым или отрицательным. Если Мэд будет покупать гитару номер i в день j, то ему нужно будет заплатить Ki·Xj бурлей.

Мэд подозревает, что некоторые производители занижают цены на свои гитары, а другие завышают. И все это — часть глобального политического заговора с целью управления массами. Поэтому он посчитал цену, за которую, как он считает, было бы справедливо продавать каждую гитару. Для гитары номер i справедливая цена равна Bi бурлей.

Привлекательность гитары номер i в день j для Мэда равна разности справедливой и фактической цены в этот день, то есть Bi - Ki·Xj.

Мэд не торопится с выбором, так как до следующего выступления группы еще целых Q дней. Необходимо каждый день до следующего выступления определять, какая гитара наиболее привлекательна для Мэда. Если в какой-то день несколько гитар обладают максимальной привлекательностью, разрешается выбрать любую.

Входные данные
В первой строке задано количество различных гитар N (1 ≤ N ≤ 105) в магазине Галактической Федерации.

Каждая из последующих N строк содержит пару целых чисел: цену гитары номер i в галактических долларах Ki (0 ≤ Ki ≤ 1000) и справедливую цену этой гитары в бурлях Bi (0 ≤ Bi ≤ 105). Цены на разные гитары могут совпадать.

В следующей строке задано количество дней до следующего выступления группы Q (1 ≤ Q ≤ 105).

В следующей строке задано Q целых чисел Xj ( - 105 ≤ Xj ≤ 105), каждое из которых соответствует курсу галактического доллара относительно бурля в день j.

Выходные данные
В единственной строке через пробел выведите Q чисел Pj, где Pj — это номер наиболее привлекательной гитары в день j.

handofkremlin    1   16.03.2020 12:14    4