В ходе полицейского расследования было выявлено подозреваемых, и теперь свидетели должны попытаться найти преступника. Был измерен рост каждого -го подозреваемого, но из-за недостоверности измерения известно лишь то, что их рост является вещественным числом из интервала от до (включительно). В лучшем случае один из подозреваемых является преступником, и может случиться так, что ни один из них не является таковым.
Один расстановка состоит из выбора двух натуральных чисел и , после чего подозреваемые отводятся в отдельную комнату, чтобы свидетели смогли попытаться опознать преступника. Поскольку свидетели могут быть сбиты с толку, если двое подозреваемых имеют одинаковый рост, то расстановка допускается только в том случае, если можно гарантировать, что никакие два подозреваемых не будут иметь одинаковый рост. Во время расстановки свидетели всегда смогут опознать преступника, если он находится среди выбранных подозреваемых, или скажут что его среди них нет.
Ведущий следователь теперь заинтересован в ответах на следующие вопросы: "Если бы я был уверен, что преступник находится только между и , то какое наименьшее количество расстановок необходимо в худшем случае, чтобы свидетели смогли найти преступника или сообщить, что он не входит в число подозреваемых?" Помогите ведущему исследователю ответить на таких вопросов.
В первой строке содержится одно натуральное число — количество подозреваемых. Следующие строк содержат два натуральных числа и , представляющие возможный диапазон роста подозреваемого номер .
Следующая строка содержит натуральное число — количество вопросов. Следующие строк содержат два натуральных числа и , определяющие вопрос.
В строках выведите ответы на соответствующие вопросы: минимально необходимое количество расстановок.