Мэд — фронтмен известной рок-группы. На последнем выступлении он разбил все свои гитары об ударную установку своего же барабанщика и теперь задумывается над покупкой новой гитары.
В магазине Галактической Федерации продаются 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.
Привлекательности гитар по дням равны соответственно: , , , , .
## Входные Данные
В первой строке задано количество различных гитар 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.
## Пример
Входные данные31 52 12 25-5 -4 -3 0 3Выходные данные3 3 1 1 1
## Примечание
Привлекательности гитар по дням равны соответственно: , , , , .
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of guitars.
Let $ K_i \in \mathbb{Z}_{\geq 0} $ be the price of guitar $ i $ in galactic dollars.
Let $ B_i \in \mathbb{Z}_{\geq 0} $ be the fair price of guitar $ i $ in burles.
Let $ Q \in \mathbb{Z}^+ $ be the number of days.
Let $ X_j \in \mathbb{Z} $ be the exchange rate (burles per galactic dollar) on day $ j $.
**Constraints**
1. $ 1 \leq N \leq 10^5 $
2. $ 0 \leq K_i \leq 1000 $
3. $ 0 \leq B_i \leq 10^5 $
4. $ 1 \leq Q \leq 10^5 $
5. $ -10^5 \leq X_j \leq 10^5 $
**Objective**
For each day $ j \in \{1, \dots, Q\} $, define the attractiveness of guitar $ i $ as:
$$
A_{i,j} = B_i - K_i \cdot X_j
$$
Find the index $ P_j \in \{1, \dots, N\} $ such that:
$$
P_j = \arg\max_{i \in \{1, \dots, N\}} A_{i,j}
$$
If multiple guitars achieve the maximum, output any such index.