403857: GYM101341 L High Probability Cast
Description
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?
InputThe 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.
OutputOutput 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.
ExamplesInput2Output
1 10
4 8
4
3 6 7 11
2 2 1 1Input
2Output
2 5
7 9
5
10 8 6 3 1
2 2 2 2 2