e-olymp
Задачи

Рой и копилки

Рой и копилки

У Роя есть n копилок пронумерованных от 1 до n. Каждый день он выбирает два индекса [l,r] и добавляет 1 монетку во все копилки начиная с l и до r (обе включительно). Он совершает такую операцию m дней.

После m дней у Роя возник вопрос: сколько копилок содержат как минимум x монет. У него q таких вопросов.

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

Первая строка содержит количество копилок n (1n106). Вторая строка содержит количество дней m (1m106). Каждая из следующих m строк содержит два целых числа l и r (1lrn). Далее следует количество запросов q (1q106). Каждая из следующих q строк содержит одно целое число x (1xn).

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
7
4
1 3
2 5
1 2
5 6
4
1
7
4
2
Выходные данные #1
6
0
0
4