L. Заклинание высокой вероятности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маг знает n заклинаний, i-е из которых при произнесении наносит случайный урон (не обязательно целый), равномерно распределённый от ai до bi. В мире обитает m монстров, причём чтобы убить j-го из них, требуется нанести ему по меньшей мере xj урона. К сожалению, монстры очень быстрые, так что маг успеет произнести лишь одно заклинание в сражении с каждым из монстров, прежде чем монстр его убьёт. Какое заклинание следует выбирать для уничтожения каждого из монстров, чтобы вероятность убить этого монстра была наибольшей?

Входные данные

Первая строка содержит единственное целое число n (1 ≤ n ≤ 200000) — количество заклинаний.

Следующие n строк описывают заклинания. Каждая из них содержит два целых числа ai и bi (1 ≤ ai ≤ bi ≤ 109) — минимальный и максимальный урон, который может нанести i-е заклинание.

Следующая строка содержит единственное целое число m (1 ≤ m ≤ 200000) — количество монстров.

Следующая строка содержит m чисел xj через пробел (1 ≤ xj ≤ 109) — минимальное количество урона, необходимое для уничтожения j-го монстра.

Выходные данные

Выведите m целых чисел через пробел, j-е из которых должно быть равно номеру заклинания, которое следует использовать для уничтожения j-го монстра. Заклинания занумерованы с единицы в порядке упоминания во входных данных. Если несколько заклинаний дают наибольшую вероятность уничтожения какого-либо монстра, можно вывести любое из этих заклинаний.

Примеры
Входные данные
2
1 10
4 8
4
3 6 7 11
Выходные данные
2 2 1 1
Входные данные
2
2 5
7 9
5
10 8 6 3 1
Выходные данные
2 2 2 2 2