Məsələlər
Рой и копилки
Рой и копилки
У Роя есть $n$ копилок пронумерованных от $1$ до $n$. Каждый день он выбирает два индекса $[l, r]$ и добавляет $1$ монетку во все копилки начиная с $l$ и до $r$ (обе включительно). Он совершает такую операцию $m$ дней.
После $m$ дней у Роя возник вопрос: сколько копилок содержат как минимум $x$ монет. У него $q$ таких вопросов.
\InputFile
Первая строка содержит количество копилок $n~(1 \le n \le 10^6)$. Вторая строка содержит количество дней $m~(1 \le m \le 10^6)$. Каждая из следующих $m$ строк содержит два целых числа $l$ и $r~(1 \le l \le r \le n)$. Далее следует количество запросов $q~(1 \le q \le 10^6)$. Каждая из следующих $q$ строк содержит одно целое число $x~(1 \le x \le n)$.
\OutputFile
Для каждого запроса выведите ответ в отдельной строке.
Giriş verilənləri #1
7 4 1 3 2 5 1 2 5 6 4 1 7 4 2
Çıxış verilənləri #1
6 0 0 4