Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача G. Объединяя усилия

Задачу добавил: alef

Успешно сдано решений: 3

Ограничение по времени на тест: 2 секунды
О граничение по памяти на тест: 256 мегабайт

Менеджеры Gadget Operating System проинформировали своих заказчиков, что менеджеры Quantum Artificial Intelligence планируют задействовать большинство сотрудников в разработке программного обеспечения для Smart Industrial Robots. А это означает сворачивание разработки программного обеспечения для устройств, которые заказчики производят.

Заказчики отреагировали на сообщение по-разному. Некоторые уже разрабатывали новые линейки продуктов, и потому были готовы рассмотреть возможность перехода на новое программное обеспечение. Некоторые задумались о том, чтобы организовать собственный отдел по разработке программного обеспечения. А один из заказчиков предложил приобрести блокирующий пакет акций Smart Industrial Robots.

Конечно, покупка достаточно крупного пакета акций — дело непростое, и для начала было решено изучить, что же собой представляет компания Smart Industrial Robots. Для этих целей было приобретено n исследований, каждое из которых охватывает некоторый отрезок времени с момента bi по момент ei включительно. Конечно, эти отрезки времени могут пересекаться.

Потенциальные приобретатели акций планируют оценить интересующую их компанию в каждый момент времени, начиная с момента s и заканчивая моментом f. Они полагают, что делать какие-либо заключения по каждому моменту времени можно, опираясь на не менее чем k различных исследований. Если какой-либо момент времени рассматривается менее, чем в k исследованиях, потенциальные приобретатели акций готовы заказать дополнительные исследования.

Ваша задача — определить суммарное количество времени, для которого понадобится заказать дополнительные исследования.

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

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

Во второй строке содержатся целые числа s и f (1 ≤ s < f ≤ 109) — начало и конец отрезка времени, интересующего приобретателей акций.

В каждой из следующих n строк содержится по два целых числа bi и ei (1 ≤ bi < ei ≤ 109) — начало и конец рассматриваемого отрезка времени.

В следующей строке содержится целое число q (1 ≤ q ≤ 105) — количество запросов.

В следующей строке содержится q целых чисел k1, k2, ..., kq (1 ≤ kj ≤ n), где kj — количество исследований, для которого нужно получить ответ на вопрос задачи.

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

Выведите q чисел t1, t2, ..., tq, где tj — суммарное количество времени, для которого потребуются дополнительные исследования, если потенциальные приобретатели акций решат опираться на не менее чем kj различных исследований.

Пример

Входные данные
5
10 20
5 12
16 19
15 25
8 14
13 17
6
2 1 3 2 4 1
Выходные данные
3 0 9 3 10 0 

Сдать задачу

Задать вопрос жюри по этой задаче