У Роя есть копилок пронумерованных от до . Каждый день он выбирает два индекса и добавляет монетку во все копилки начиная с и до (обе включительно). Он совершает такую операцию дней.
После дней у Роя возник вопрос: сколько копилок содержат как минимум монет. У него таких вопросов.
Первая строка содержит количество копилок . Вторая строка содержит количество дней . Каждая из следующих строк содержит два целых числа и . Далее следует количество запросов . Каждая из следующих строк содержит одно целое число .
Для каждого запроса выведите ответ в отдельной строке.