Statement is not available in English language
F. Ксюша и экзамен по алгебре
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ксюша поступила в престижный университет на Кипре. Программа первого семестра по алгебре содержала только лишь темы «Умножение целых чисел» и «Деление целых чисел». Ксюша училась в лучшей школе страны и уже проходила эти темы, поэтому она решила прогуливать лекции и семинары по алгебре.

Когда выпал снег и наступила сессия, Ксюша пришла на экзамен. Экзаменатор был восмущён пропусками Ксюши и решил её завалить, дав самую сложную задачу.

Дан массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Необходимо ответить на $$$m$$$ запросов. Запросы бывают трёх типов:

  1. посчитать $$$a_l \cdot a_{l+1} \cdot \ldots \cdot a_r$$$ по модулю $$$10^9 + 7$$$;
  2. поделить каждое из чисел $$$a_l, a_{l+1}, \ldots, a_r$$$ на его минимальный нечётный делитель, больший $$$1$$$; если такого нет, число не меняется;
  3. присвоить $$$a_i = x$$$.

Ксюша не хочет отчисляться и уезжать с Кипра, помогите ей сдать экзамен.

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

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следует описание наборов.

В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество элементов в массиве.

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 5 \cdot 10^5$$$) — элементы массива.

В третьей строке дано целое число $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — количество запросов.

В следующих $$$m$$$ строках даны запросы:

  • ? $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$) — запрос произведения по модулю $$$10^9 + 7$$$ на отрезке;
  • / $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$) — запрос массового деления на отрезке;
  • = $$$i$$$ $$$x$$$ ($$$1 \le i \le n$$$, $$$1 \le x \le 5 \cdot 10^5$$$) — запрос изменения элемента.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. То же самое гарантируется для $$$m$$$.

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

Для каждого набора входных данных выведите ответы на запросы типа «?» в отдельных строках.

Пример
Входные данные
2
4
15 62 41 16
8
? 1 4
/ 1 4
? 1 4
/ 1 4
? 1 4
/ 1 4
= 2 228
? 1 4
6
1 500000 100500 1234 777 101
7
= 3 303
? 2 4
/ 1 3
? 1 5
/ 2 6
= 5 13
? 4 6
Выходные данные
610080
160
32
3648
950998698
61732212
26
Примечание

В первом наборе входных данных после применения первой операции деления массив трансформируется так:

$$$15, 62, 41, 16 \to \frac{15}{3}, \frac{62}{31}, \frac{41}{41}, 16 = 5, 2, 1, 16$$$