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

1850. Космический туризм

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
В звёздной системе Бетельгейзе n планет. Каждая планета населена некоторой разумной расой, на разных планетах могут обитать одинаковые расы. Все планеты вращаются вокруг Бетельгейзе по круговым орбитам с одинаковой угловой скоростью и лежат на луче, начинающемся из звезды. В министерство космического туризма часто обращаются туристы-одиночки из других галактик, которые хотят, чтобы их вместе с их личным кораблём доставили на какую-нибудь планету, откуда они смогли бы отправиться в путешествие по планетам системы.
Корабли всех туристов снабжены небольшим топливным баком, который позволяет покрыть без дозаправки расстояние не более d астрономических единиц. На любой планете системы можно заправить топливный бак до максимума. Кроме того, для каждого корабля известен диапазон расстояний до звезды, в которых он может нормально функционировать, используя энергию излучения звезды. Туриста можно доставить на планету только в том случае, если расстояние от этой планеты до звезды попадает в данный диапазон.
Министерство поручило вам вычислить для каждого туриста максимальное количество рас, с которыми он сможет установить контакт.

Исходные данные

В первой строке через пробел записаны целые числа n, s и d (1 ≤ n, s, d ≤ 105) — количество планет в системе Бетельгейзе, количество известных науке рас и максимальное расстояние, которое могут пролететь корабли туристов без дозаправки. В каждой из следующих n строк через пробел записаны два целых положительных числа — расстояние от очередной планеты системы до звезды и номер расы, населяющей эту планету. Расы занумерованы целыми числами от 1 до s. Расстояния от Бетельгейзе до всех планет различны и не превосходят 106 астрономических единиц. В следующей строке записано целое число m (1 ≤ m ≤ 105) — количество туристов. В каждой из следующих m строк через пробел записаны два целых положительных числа — минимальное и максимальное расстояние до звезды, на котором может находиться корабль очередного туриста. Эти расстояния не превосходят 106.

Результат

Для каждого туриста выведите в отдельной строке максимальное количество рас, с которыми он сможет познакомиться

Пример

исходные данныерезультат
5 5 11
10 1
50 2
30 1
20 1
60 3
2
5 65
15 45
2
1
Автор задачи: Дмитрий Иванков
Источник задачи: Ural SU Contest. Petrozavodsk Summer Session, August 2010