Задачі
Рой і скарбнички
Рой і скарбнички
У Роя є $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** ≤ **l** ≤ **r** ≤ **n**). Далі слідує кількість запитів **q** (**1** ≤ **q** ≤ `10^6`). Кожен з таких **q** рядків містить одне ціле число **x** (**1** ≤ **x** ≤ **n**).
\OutputFile
Для кожного запиту виведіть відповідь в окремому рядку.
Вхідні дані #1
7 4 1 3 2 5 1 2 5 6 4 1 7 4 2
Вихідні дані #1
6 0 0 4