Codeforces Round 675 (Div. 2) |
---|
Закончено |
У Юры есть очень самый обыкновенный и скучный массив $$$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
Пояснение к примеру:
Название |
---|