На прямой лежат n отрезков. Для каждой пары отрезков известно, что они либо не имеют общих точек, либо все точки одного из них также принадлежат и другому отрезку.
Дано m запросов. Каждый запрос представляет собой точку на прямой. Найдите для каждого запроса отрезок минимальной длины, которому принадлежит эта точка.
Исходные данные
В первой строке записано целое число n — количество отрезков (1 ≤ n ≤ 105). i-я из следующих n строк содержит целые числа ai и bi — координаты концов i-го отрезка (1 ≤ ai < bi ≤ 109).
Отрезки упорядочены по неубыванию ai, а при ai = aj —
по убыванию длины. Совпадающих отрезков нет. В следующей строке записано целое число m — количество запросов (1 ≤ m ≤ 105).
В j-й из следующих m строк записано целое число cj — координата точки
(1 ≤ cj ≤ 109). Запросы упорядочены по неубыванию cj.
Результат
Для каждого запроса выведите номер искомого отрезка в отдельной строке. Если точка не принадлежит ни одному отрезку, выведите «-1». Отрезки пронумерованы числами от 1 до n в том порядке, в котором они перечислены во входных данных.
Пример
исходные данные | результат |
---|
3
2 10
2 3
5 7
11
1
2
3
4
5
6
7
8
9
10
11
| -1
2
2
1
3
3
3
1
1
1
-1
|
Автор задачи: Михаил Рубинчик (идея — Никита Первухин)
Источник задачи: Открытый командный чемпионат УрФУ по программированию — 2013