F. Скучные запросы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Юры есть очень самый обыкновенный и скучный массив $$$a$$$ длины $$$n$$$. Казалось бы, ничего скучнее быть не может, но Владик так не думает!

Чтобы сделать массив Юры более скучным, Владик решил сделать $$$q$$$ скучных запросов. Каждый запрос состоит из двух целых чисел $$$x$$$ и $$$y$$$. Далее для вычисления границ $$$l$$$ и $$$r$$$ данного запроса используется формула: $$$l = (last + x) \bmod n + 1$$$, $$$r = (last + y) \bmod n + 1$$$, где $$$last$$$ — это ответ на предыдущий запрос (изначально он равен нулю), а $$$\bmod$$$ — это операция взятия остатка от деления. Если получилось, что $$$l > r$$$, то их значения нужно поменять местами.

Когда Владик наконец посчитал границы $$$l$$$ и $$$r$$$ для текущего запроса, то он захотел узнать значение наименьшего общего кратного (НОК) на отрезке $$$[l; r]$$$ для исходного массива $$$a$$$ по модулю $$$10^9 + 7$$$. НОК некоторого набора элементов — это наименьшее натуральное число, которое делится на каждое из чисел данного набора. Посчитанный НОК будет являться ответом на текущий запрос.

Помогите Владику и выведите ответ на каждый запрос!

Входные данные

Первая строка ввода содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество элементов массива.

Следующая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — описание элементов массива.

Третья строка ввода содержит единственное целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.

Следующие $$$q$$$ строк содержат по два целых числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$) — описание очередного запроса.

Выходные данные

Выведите $$$q$$$ целых чисел — ответ на каждый запрос.

Пример
Входные данные
3
2 3 5
4
1 3
3 3
2 3
2 3
Выходные данные
6
2
15
30
Примечание

Пояснение к примеру:

  • границы первого запроса $$$(0 + 1) \bmod 3 + 1 = 2$$$ и $$$(0 + 3) \bmod 3 + 1 = 1$$$. НОК на отрезке $$$[1, 2]$$$ равен $$$6$$$;
  • границы второго запроса $$$(6 + 3) \bmod 3 + 1 = 1$$$ и $$$(6 + 3) \bmod 3 + 1 = 1$$$. НОК на отрезке $$$[1, 1]$$$ равен $$$2$$$;
  • границы третьего запроса $$$(2 + 2) \bmod 3 + 1 = 2$$$ и $$$(2 + 3) \bmod 3 + 1 = 3$$$. НОК на отрезке $$$[2, 3]$$$ равен $$$15$$$;
  • границы четвертого запроса $$$(15 + 2) \bmod 3 + 1 = 3$$$ и $$$(15 + 3) \bmod 3 + 1 = 1$$$. НОК на отрезке $$$[1, 3]$$$ равен $$$30$$$.