{"raw_statement":[{"iden":"statement","content":"A mage knows n spells, the i-th of which, when casted, deals random damage (not necessarily integer), uniformly distributed from ai to bi. There are m monsters dwelling in the world, and to kill the j-th of them it is required to deal him at least xj damage. Unfortunately, monsters are so fast that the mage has time to cast only a single spell while fighting each of the monsters, before being killed by that monster. Which spell should be chosen to destroy each of the monsters, so that the probability of killing that monster would be maximized?\n\nThe first line contains a single integer n (1 ≤ n ≤ 200000) — the number of spells.\n\nThe next n lines describe spells. Each of them contains two integers ai and bi (1 ≤ ai ≤ bi ≤ 109) — the minimal and maximal damage the i-th spell can deal.\n\nThe next line contains a single integer m (1 ≤ m ≤ 200000) — the number of monsters.\n\nThe next line contains m integers xj separated by a space (1 ≤ xj ≤ 109) — the minimal amount of damage required to destroy the j-th monster.\n\nOutput m integers separated by a space, the j-th of which should be equal to the number of spell which should be used to destroy the j-th monster. The spells are numbered from one in the order they are listed in the input. If there are many spells which give the maximal probability of destroying some monster, you can output any of these spells.\n\n"},{"iden":"input","content":"The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of spells.The next n lines describe spells. Each of them contains two integers ai and bi (1 ≤ ai ≤ bi ≤ 109) — the minimal and maximal damage the i-th spell can deal.The next line contains a single integer m (1 ≤ m ≤ 200000) — the number of monsters.The next line contains m integers xj separated by a space (1 ≤ xj ≤ 109) — the minimal amount of damage required to destroy the j-th monster."},{"iden":"output","content":"Output m integers separated by a space, the j-th of which should be equal to the number of spell which should be used to destroy the j-th monster. The spells are numbered from one in the order they are listed in the input. If there are many spells which give the maximal probability of destroying some monster, you can output any of these spells."},{"iden":"examples","content":"Input21 104 843 6 7 11Output2 2 1 1 Input22 57 9510 8 6 3 1Output2 2 2 2 2 "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $.  \nLet $ \\mathcal{S} = \\{ (a_i, b_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of spells, where $ a_i, b_i \\in \\mathbb{R} $, $ 1 \\le a_i \\le b_i \\le 10^9 $.  \nLet $ \\mathcal{M} = \\{ x_j \\mid j \\in \\{1, \\dots, m\\} \\} $ be the set of monster thresholds, where $ x_j \\in \\mathbb{R} $, $ 1 \\le x_j \\le 10^9 $.  \n\nFor spell $ i $, the damage $ D_i \\sim \\text{Uniform}(a_i, b_i) $.  \nThe probability that spell $ i $ kills monster $ j $ is:  \n$$\nP_{i,j} = \\begin{cases}\n0 & \\text{if } b_i < x_j \\\\\n\\frac{b_i - x_j}{b_i - a_i} & \\text{if } a_i \\le x_j \\le b_i \\\\\n1 & \\text{if } a_i \\ge x_j\n\\end{cases}\n$$\n\n**Constraints**  \n1. $ 1 \\le n \\le 200000 $  \n2. $ 1 \\le m \\le 200000 $  \n3. $ 1 \\le a_i \\le b_i \\le 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ 1 \\le x_j \\le 10^9 $ for all $ j \\in \\{1, \\dots, m\\} $\n\n**Objective**  \nFor each monster $ j \\in \\{1, \\dots, m\\} $, find:  \n$$\n\\arg\\max_{i \\in \\{1, \\dots, n\\}} P_{i,j}\n$$  \nOutput the index $ i $ (1-based) of any spell achieving this maximum.","simple_statement":"For each monster, choose the spell that maximizes the chance of dealing at least the required damage. Each spell deals random damage between ai and bi. Output the spell number (1-indexed) for each monster.","has_page_source":false}