Ước chung trong đoạn

Cho hai số nguyên dương $a$ và $b$. Với mỗi truy vấn gồm hai số $low$ và $high$, hãy tìm ước chung lớn nhất của $a$ và $b$ nằm trong đoạn $[low,high]$ (tính cả hai đầu mút).

Nói cách khác, cần tìm số $d$ lớn nhất sao cho $a$ chia hết cho $d$, $b$ chia hết cho $d$, và $low\le d\le high$. Nếu không tồn tại số $d$ như vậy, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $a$ và $b$.
• Dòng thứ hai chứa số nguyên $n$, số lượng truy vấn.
• $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $low$ và $high$ mô tả một truy vấn.

Dữ liệu ra

In ra $n$ dòng, dòng thứ $i$ là kết quả của truy vấn thứ $i$: ước chung lớn nhất của $a$ và $b$ nằm trong đoạn $[low,high]$, hoặc $-1$ nếu không có.

Ràng buộc

• $1\le a,b\le {10}^9$
• $1\le n\le {10}^4$
• $1\le low\le high\le {10}^9$

Ví dụ