Задача G. Объединяя усилия
Задачу добавил: alef
Успешно сдано решений: 3
Менеджеры 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