{"raw_statement":[{"iden":"statement","content":"Мэд — фронтмен известной рок-группы. На последнем выступлении он разбил все свои гитары об ударную установку своего же барабанщика и теперь задумывается над покупкой новой гитары.\n\nВ магазине Галактической Федерации продаются N различных гитар, гитара номер i стоит Ki галактических долларов. Однако Мэд живет в Соединенном Королевстве Берляндии, поэтому в наличии у Мэда только бурли. Курс галактического доллара относительно бурля абсолютно непредсказуем и меняется каждый день, в день j он равен Xj бурлей за доллар. При этом курс может быть нулевым или отрицательным. Если Мэд будет покупать гитару номер i в день j, то ему нужно будет заплатить Ki·Xj бурлей.\n\nМэд подозревает, что некоторые производители занижают цены на свои гитары, а другие завышают. И все это — часть глобального политического заговора с целью управления массами. Поэтому он посчитал цену, за которую, как он считает, было бы справедливо продавать каждую гитару. Для гитары номер i справедливая цена равна Bi бурлей.\n\nПривлекательность гитары номер i в день j для Мэда равна разности справедливой и фактической цены в этот день, то есть Bi - Ki·Xj.\n\nМэд не торопится с выбором, так как до следующего выступления группы еще целых Q дней. Необходимо каждый день до следующего выступления определять, какая гитара наиболее привлекательна для Мэда. Если в какой-то день несколько гитар обладают максимальной привлекательностью, разрешается выбрать любую.\n\nВ первой строке задано количество различных гитар N (1 ≤ N ≤ 105) в магазине Галактической Федерации.\n\nКаждая из последующих N строк содержит пару целых чисел: цену гитары номер i в галактических долларах Ki (0 ≤ Ki ≤ 1000) и справедливую цену этой гитары в бурлях Bi (0 ≤ Bi ≤ 105). Цены на разные гитары могут совпадать.\n\nВ следующей строке задано количество дней до следующего выступления группы Q (1 ≤ Q ≤ 105).\n\nВ следующей строке задано Q целых чисел Xj ( - 105 ≤ Xj ≤ 105), каждое из которых соответствует курсу галактического доллара относительно бурля в день j.\n\nВ единственной строке через пробел выведите Q чисел Pj, где Pj — это номер наиболее привлекательной гитары в день j.\n\nПривлекательности гитар по дням равны соответственно: , , , , .\n\n"},{"iden":"входные данные","content":"В первой строке задано количество различных гитар N (1 ≤ N ≤ 105) в магазине Галактической Федерации.Каждая из последующих N строк содержит пару целых чисел: цену гитары номер i в галактических долларах Ki (0 ≤ Ki ≤ 1000) и справедливую цену этой гитары в бурлях Bi (0 ≤ Bi ≤ 105). Цены на разные гитары могут совпадать.В следующей строке задано количество дней до следующего выступления группы Q (1 ≤ Q ≤ 105).В следующей строке задано Q целых чисел Xj ( - 105 ≤ Xj ≤ 105), каждое из которых соответствует курсу галактического доллара относительно бурля в день j."},{"iden":"выходные данные","content":"В единственной строке через пробел выведите Q чисел Pj, где Pj — это номер наиболее привлекательной гитары в день j."},{"iden":"пример","content":"Входные данные31 52 12 25-5 -4 -3 0 3Выходные данные3 3 1 1 1 "},{"iden":"примечание","content":"Привлекательности гитар по дням равны соответственно: , , , , ."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of guitars.  \nLet $ K_i \\in \\mathbb{Z}_{\\geq 0} $ be the price of guitar $ i $ in galactic dollars.  \nLet $ B_i \\in \\mathbb{Z}_{\\geq 0} $ be the fair price of guitar $ i $ in burles.  \nLet $ Q \\in \\mathbb{Z}^+ $ be the number of days.  \nLet $ X_j \\in \\mathbb{Z} $ be the exchange rate (burles per galactic dollar) on day $ j $.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $  \n2. $ 0 \\leq K_i \\leq 1000 $  \n3. $ 0 \\leq B_i \\leq 10^5 $  \n4. $ 1 \\leq Q \\leq 10^5 $  \n5. $ -10^5 \\leq X_j \\leq 10^5 $\n\n**Objective**  \nFor each day $ j \\in \\{1, \\dots, Q\\} $, define the attractiveness of guitar $ i $ as:  \n$$\nA_{i,j} = B_i - K_i \\cdot X_j\n$$  \nFind the index $ P_j \\in \\{1, \\dots, N\\} $ such that:  \n$$\nP_j = \\arg\\max_{i \\in \\{1, \\dots, N\\}} A_{i,j}\n$$  \nIf multiple guitars achieve the maximum, output any such index.","simple_statement":"You are given N guitars. Each guitar i has a price Ki (in galactic dollars) and a fair price Bi (in burlys).  \n\nEach day j, the exchange rate is Xj (burlys per galactic dollar).  \n\nThe attractiveness of guitar i on day j is: Bi - Ki * Xj.  \n\nFor each of Q days, find the guitar with the HIGHEST attractiveness.  \n\nIf multiple guitars tie, pick any.  \n\nOutput the guitar number (1-indexed) for each day.","has_page_source":false}