Мэд — фронтмен известной рок-группы. На последнем выступлении он разбил все свои гитары об ударную установку своего же барабанщика и теперь задумывается над покупкой новой гитары.
В магазине Галактической Федерации продаются 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.
Вход G(5), вызов F(4)+2G(4)
Вход F(4), вызов 2F(3)-G(3)
Вход F(3), вызов 2F(2)-G(2)
Вход F(2), вызов 2F(1)-G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(2), вызов F(1)+2G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(3), вызов F(2)+2G(2)
Вход F(2), вызов 2F(1)-G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(2), вызов F(1)+2G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(4), вызов F(3)+2G(3)
Вход F(3), вызов 2F(2)-G(2)
Вход F(2), вызов 2F(1)-G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(2), вызов F(1)+2G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(3), вызов F(2)+2G(2)
Вход F(2), вызов 2F(1)-G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(2), вызов F(1)+2G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход F(5), вызов 2F(4)-G(4)
Вход F(4), вызов 2F(3)-G(3)
Вход F(3), вызов 2F(2)-G(2)
Вход F(2), вызов 2F(1)-G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(2), вызов F(1)+2G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(3), вызов F(2)+2G(2)
Вход F(2), вызов 2F(1)-G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(2), вызов F(1)+2G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(4), вызов F(3)+2G(3)
Вход F(3), вызов 2F(2)-G(2)
Вход F(2), вызов 2F(1)-G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(2), вызов F(1)+2G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(3), вызов F(2)+2G(2)
Вход F(2), вызов 2F(1)-G(1)
Вход F(1), результат 1
Вход G(1), результат 1
Вход G(2), вызов F(1)+2G(1)
Вход F(1), результат 1
Вход G(1), результат 1
-14
-> означает что от этого слова идут 2 стрелки и в конце стрелок слово.
магнитный диск -> sport -> sky -> russia.txt
магнитный диск -> sport -> skate -> getmany.txt
= = = =
магнитный диск -> computer -> bm -> info -> pentium.txt
магнитный диск -> computer -> info -> ibm.txt
объясняю: от магнитного диска идёт 2 ветви(это же дерево) 1.sport и 2.computer
1.от ветки sport идёт ещё 2 ветки sky и skate
от ветки sky идёт "плод" - russia.txt
от ветки skate идёт "плод" - germany.txt
2.от ветки computer идёт 2 ветки - 1.bm и 2.info
от ветки bm идёт info ,а от info "плод" - pentium.txt
от ветки info идёт "плод" - ibm.txt
получается вот такое дерево)