L. High Probability Cast
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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?

Input

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.

Output

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.

Examples
Input
2
1 10
4 8
4
3 6 7 11
Output
2 2 1 1 
Input
2
2 5
7 9
5
10 8 6 3 1
Output
2 2 2 2 2