Возводи в степень и суммируй!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аналитик Жора работает в маленькой компании, где он должен выполнять определенные вычисления. Еще десять лет назад ему выдали массив чисел. После этого каждый день он должен был вычислять сумму чисел на отрезке, концы которого задавали ему утром.

Жора изучал программирование в МИСИС, поэтому без труда написал программу, которая автоматически вычисляет требуемую сумму. Благодаря этому у Жоры была возможность весь день пить чай с печеньем и читать классику мировой литературы.

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

Новость очень шокировала Жору, ведь его привычный уклад жизни был под угрозой. Он сразу понял, что нужно переписать свою программу таким образом, чтобы она выполняла еще и изменения массива. Но за десять лет чтения классической литературы Жора подзабыл основы программирования.

Помогите Жоре написать программу, которая будет вычислять запросы и выполнять изменения в массиве.

Будем считать, что массив Жоры состоит из $$$n$$$ целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$. Запросы, которые необходимо выполнять, бывают трех типов:

- $$$1$$$ $$$k$$$ — запрос первого типа, в котором необходимо все элементы массива возвести в степень $$$k$$$. Если после выполнения этого запроса хотя бы одно число станет больше, чем $$$10^5$$$, то этот запрос нужно проигнорировать.

- $$$2$$$ $$$k$$$ — запрос второго типа, в котором необходимо из всех элементов массива извлечь корень степени $$$k$$$. Если после выполнения этого запроса хотя бы одно число перестанет быть целым, то этот запрос нужно проигнорировать.

- $$$3$$$ $$$l$$$ $$$r$$$ — запрос третьего типа, в котором необходимо вычислить сумму элементов с номерами от $$$l$$$ до $$$r$$$ включительно.

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

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

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

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

В следующих $$$q$$$ строках заданы запросы по одному в строке. Запросы бывают трех видов:

- $$$1$$$ $$$k$$$ ($$$2 \le k \le 10^5$$$) — запрос первого типа.

- $$$2$$$ $$$k$$$ ($$$2 \le k \le 10^5$$$) — запрос второго типа.

- $$$3$$$ $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$) — запрос третьего типа.

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

На каждый запрос третьего типа выведите в отдельной строке ответ на этот запрос.

Примеры

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

    51 2 3 4 5143 1 51 23 1 51 23 1 52 33 1 52 43 1 53 1 13 2 23 3 33 4 43 5 5

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

    15
    55
    979
    979
    15
    1
    2
    3
    4
    5

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

    11231 62 33 1 1

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

    12