Модифікований НСД

Знайдіть найбільший спільний дільник $d$ двох цілих чисел $a$ і $b$, який належить відрізку цілих чисел $[low,high](low\le high)$, тобто такий, що $low\le d\le high$.

Може трапитися, що у заданому відрізку немає спільних дільників.

Дано два цілі числа $a$ і $b$, а також $n$ запитів. Кожен запит — це певний відрізок $[low,high]$. Напишіть програму, яка обробить всі задані запити.

Вхідні дані

У першому рядку записано два цілі числа $a$ і $b(1\le a,b\le 10^9)$. У другому рядку міститься кількість запитів $n(1\le n\le 10^4)$. Далі слідує $n$ рядків. Кожен рядок містить один запит — два цілі числа $low$ і $high(1\le low\le high\le 10^9)$.

Вихідні дані

Виведіть $n$ рядків, $i$-ий з яких повинен містити відповідь на $i$-ий запит. Якщо у даному відрізку спільних дільників немає, виведіть $-1$.

Приклади