ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1987. Вложенные отрезки

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
На прямой лежат 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