D. Куб на отрезке
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

Дана последовательность целых чисел a1, a2, ..., an. Надо выполнить q запросов, каждый запрос относится к одному из двух следующих типов:

  1. Даны два целых числа, l и r (1 ≤ l ≤ r ≤ n), найдите сумму всех элементов в последовательности al, al + 1, ..., ar.
  2. Даны два целых числа, l и r (1 ≤ l ≤ r ≤ n), возведите каждый элемент в последовательности al, al + 1, ..., ar в куб. То есть выполните присвоения al = al3, al + 1 = al + 13, ..., ar = ar3.

Для каждого запроса типа 1 выведите ответ на него.

Сам Тайни, конечно, никак не додумается — так что он просит Вас помочь ему. При этом, Тайни обожает простые числа. Поэтому он сказал Вам, что, так как ответ может быть слишком большим, его стоит выводить по модулю 95542721 (это число является простым).

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

В первой строке записано целое число n (1 ≤ n ≤ 105), обозначающее длину последовательности. Во второй строке записано n целых чисел через пробел a1, a2, ..., an (0 ≤ ai ≤ 109).

В третьей строке записано целое число q (1 ≤ q ≤ 105), обозначающее количество запросов. Затем следуют q строк. В каждой строке записано по три целых числа ti (1 ≤ ti ≤ 2), li, ri (1 ≤ li ≤ ri ≤ n), где ti обозначает тип запроса, а li и ri — параметры запроса, соответственно.

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

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

Обратите внимание, что каждое выведенное число должно быть неотрицательным и должно быть меньше 95542721.

Примеры
Входные данные
8
1 2 3 4 5 6 7 8
5
1 2 5
2 2 5
1 2 5
2 3 6
1 4 7
Выходные данные
14
224
2215492