НСД запити
Вам дано масив цілих невід'ємних чисел довжини і запитів. Кожен запит — два числа та . Для кожного запиту знайдіть максимум по попарних найбільших спільних дільниках підмасиву від до , тобто:
Вхідні дані
Перший рядок містить одне ціле число () — розмір масиву.
Другий рядок містить цілих чисел () — елементи масиву.
Третій рядок містить одне ціле число () — кількість запитів.
-ий з наступних рядків містить два цілі числа , () — межі запиту.
Вихідні дані
Для кожного запиту виведіть одне ціле число — відповідь на нього.
Приклади
Примітка
— найбільший спільний дільник чисел .
Розглянемо другий приклад:
У перших чотирьох запитах відрізок складається лише з двох чисел, отже відповідь — їхній найбільший спільний дільник.
Запит : найбільший спільний дільник має числа та , .
Запит : потрібно порахувати .
Запит : потрібно порахувати .
Оцінювання
( балів): ;
( балів): ;
( балів): ;
( балів): всі — степені двійок;
( балів): ;
( балів): ;
( балів): без додаткових обмежень.