eolymp
Задачі

Рой і скарбнички

Рой і скарбнички

У Роя є * 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