{"problem":{"name":"C. Неестественный отбор","description":{"content":"Мэд — фронтмен известной рок-группы. На последнем выступлении он разбил все свои гитары об ударную установку своего же барабанщика и теперь задумывается над покупкой новой гитары. В магазине Галактич","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10136C"},"statements":[{"statement_type":"Markdown","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## Входные Данные\n\nВ первой строке задано количество различных гитар N (1 ≤ N ≤ 105) в магазине Галактической Федерации.Каждая из последующих N строк содержит пару целых чисел: цену гитары номер i в галактических долларах Ki (0 ≤ Ki ≤ 1000) и справедливую цену этой гитары в бурлях Bi (0 ≤ Bi ≤ 105). Цены на разные гитары могут совпадать.В следующей строке задано количество дней до следующего выступления группы Q (1 ≤ Q ≤ 105).В следующей строке задано Q целых чисел Xj ( - 105 ≤ Xj ≤ 105), каждое из которых соответствует курсу галактического доллара относительно бурля в день j.\n\n## Выходные Данные\n\nВ единственной строке через пробел выведите Q чисел Pj, где Pj — это номер наиболее привлекательной гитары в день j.\n\n## Пример\n\nВходные данные31 52 12 25-5 -4 -3 0 3Выходные данные3 3 1 1 1 \n\n## Примечание\n\nПривлекательности гитар по дням равны соответственно: , , , , .\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10136C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}