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

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

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

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

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

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

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