{"raw_statement":[{"iden":"statement","content":"В надежде посчитать, сколько тетрадей в клеточку он сможет купить, Ваня создал портал в параллельные миры. К сожалению, от этого его дела пошли только хуже: теперь, вместо того, чтобы определить максимальное число тетрадей, которые можно купить, для одного мира, ему требуется решить эту задачу для $m$ миров. К счастью, отличие всех миров заключается только в том, сколько денег есть у Вани, тогда как цены в магазинах и количество доступных для покупки тетрадей во всех мирах одинаковы.\n\n*Обратите внимание, что ограничения на $a_i$ и $b_i$ отличаются от ограничений в задаче $C$!*\n\nПомогите Ване справиться с новыми трудностями!\n\nВ первой строке записаны два целых числа $n$ и $m$ ($1 <= n, m <= 10^5$) - количество магазинов и количество миров соответственно.\n\nВо второй строке записано $m$ чисел $k_i$, где $k_i$ означает число монет Вани в $i$-м мире ($1 <= k_i <= 10^(18)$).\n\nВ следующих $n$ строках записано по два целых числа $a_i$, $b_i$ ($1 <= a_i <= 10^9$, $1 <= b_i <= 4 * 10^4$) – цена тетради в клеточку в $i$-м магазине и количество имеющихся в нём в наличии тетрадей соответственно.\n\nВыведите $m$ чисел, где $i$-е число означает максимальное число тетрадей, которое может купить Ваня в $i$-м мире.\n\n"},{"iden":"входные данные","content":"В первой строке записаны два целых числа $n$ и $m$ ($1 <= n, m <= 10^5$) - количество магазинов и количество миров соответственно.Во второй строке записано $m$ чисел $k_i$, где $k_i$ означает число монет Вани в $i$-м мире ($1 <= k_i <= 10^(18)$).В следующих $n$ строках записано по два целых числа $a_i$, $b_i$ ($1 <= a_i <= 10^9$, $1 <= b_i <= 4 * 10^4$) – цена тетради в клеточку в $i$-м магазине и количество имеющихся в нём в наличии тетрадей соответственно."},{"iden":"выходные данные","content":"Выведите $m$ чисел, где $i$-е число означает максимальное число тетрадей, которое может купить Ваня в $i$-м мире."},{"iden":"пример","content":"Входные данные2 3\n10 30 20\n8 2\n5 2\nВыходные данные2 4 3 "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of dictionary words.  \nLet $ S = (s_1, s_2, \\dots, s_N) $ be the dictionary, where each $ s_j $ is a string over $ \\Sigma = \\{a, b, \\dots, z\\} $.  \n\nLet $ M \\in \\mathbb{Z} $ be the number of text words.  \nLet $ T = (t_1, t_2, \\dots, t_M) $ be the text, where each $ t_i $ is a string over $ \\Sigma $.  \n\nA word $ t_i \\in T $ is an *abbreviation* of a dictionary word $ s_j \\in S $ if $ t_i $ is a subsequence of $ s_j $ and $ |t_i| < |s_j| $.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 500 $  \n2. $ \\sum_{j=1}^N |s_j| \\leq 2 \\times 10^6 $  \n3. $ 1 \\leq M \\leq 2000 $  \n4. $ 1 \\leq |t_i| \\leq 10 $ for all $ i \\in \\{1, \\dots, M\\} $  \n5. All strings consist only of lowercase Latin letters.  \n6. For each $ t_i $, there is at most one $ s_j \\in S $ such that $ t_i $ is an abbreviation of $ s_j $.  \n\n**Objective**  \nFor each $ i \\in \\{1, \\dots, M\\} $:  \n- If $ t_i $ is an abbreviation of some $ s_j \\in S $, output $ s_j $.  \n- Otherwise, output $ t_i $.","simple_statement":"Peter hates abbreviations. His predecessor used many abbreviations in the code. Luckily, before leaving, he made a dictionary: a list of N full words that were abbreviated.\n\nPeter has a text of M words. A word in the text is an abbreviation of a dictionary word if it matches the first few letters of that full word (prefix match).\n\nHelp Peter replace every abbreviated word in the text with its full dictionary word. If a word is not an abbreviation, leave it unchanged.\n\nInput:\n- First line: N (number of dictionary words)\n- Next N lines: full dictionary words\n- Next line: M (number of text words)\n- Next M lines: words in the text\n\nOutput:\n- M lines: the text after replacing all abbreviations with full words","has_page_source":false}