Модифікований НСД#11260
Знайдіть найбільший спільний дільник двох цілих чисел і , який належить відрізку цілих чисел [low, high]~(low \le high), тобто такий, що low \le d \le high.
Може трапитися, що у заданому відрізку немає спільних дільників.
Дано два цілі числа і , а також запитів. Кожен запит — це певний відрізок [low, high]. Напишіть програму, яка обробить всі задані запити.
У першому рядку записано два цілі числа і b~(1 \le a, b \le 10^9). У другому рядку міститься кількість запитів n~(1 \le n \le 10^4). Далі слідує рядків. Кожен рядок містить один запит — два цілі числа і high~(1 \le low \le high \le 10^9).
Виведіть рядків, -ий з яких повинен містити відповідь на -ий запит. Якщо у даному відрізку спільних дільників немає, виведіть .
Приклад 1