Задачи
Рой и копилки
Рой и копилки
У Роя есть n копилок пронумерованных от 1 до n. Каждый день он выбирает два индекса [l,r] и добавляет 1 монетку во все копилки начиная с l и до r (обе включительно). Он совершает такую операцию m дней.
После m дней у Роя возник вопрос: сколько копилок содержат как минимум x монет. У него q таких вопросов.
Входные данные
Первая строка содержит количество копилок n (1 ≤ n ≤ 10^6). Вторая строка содержит количество дней m (1 ≤ m ≤ 10^6). Каждая из следующих m строк содержит два целых числа l и r (1 ≤ l ≤ r ≤ n). Далее следует количество запросов q (1 ≤ q ≤ 10^6). Каждая из следующих q строк содержит одно целое число x (1 ≤ x ≤ n).
Выходные данные
Для каждого запроса выведите ответ в отдельной строке.
Пример
Входные данные #1
7 4 1 3 2 5 1 2 5 6 4 1 7 4 2
Выходные данные #1
6 0 0 4