A9012. Interval Cubing

While learning Computational Geometry, Tiny is simultaneously learning a useful data structure called segment tree or interval tree. He has scarcely grasped it when comes out a strange problem:

Given an integer sequence $a_{1},a_{2},...,a_{n}$ . You should run $q$ queries of two types:

1. Given two integers $l$ and $r$ ( $1<=l<=r<=n$ ), ask the sum of all elements in the sequence $a_{l},a_{l+1},...,a_{r}$ .
2. Given two integers $l$ and $r$ ( $1<=l<=r<=n$ ), let each element $x$ in the sequence $a_{l},a_{l+1},...,a_{r}$ becomes $x^{3}$ . In other words, apply an assignments $a_{l}=a_{l}^{3},a_{l+1}=a_{l+1}^{3},...,a_{r}=a_{r}^{3}$ .

For every query of type 1, output the answer to it.

Tiny himself surely cannot work it out, so he asks you for help. In addition, Tiny is a prime lover. He tells you that because the answer may be too huge, you should only output it modulo $95542721$ (this number is a prime number).

The first line contains an integer $n$ ( $1<=n<=10^{5}$ ), representing the length of the sequence. The second line contains $n$ space-separated integers $a_{1},a_{2},...,a_{n}$ ( $0<=a_{i}<=10^{9}$ ).

The third line contains an integer $q$ ( $1<=q<=10^{5}$ ), representing the number of queries. Then follow $q$ lines. Each line contains three integers $t_{i}$ ( $1<=t_{i}<=2$ ), $l_{i}$ , $r_{i}$ ( $1<=l_{i}<=r_{i}<=n$ ), where $t_{i}$ stands for the type of the query while $l_{i}$ and $r_{i}$ is the parameters of the query, correspondingly.

For each 1-type query, print the answer to it per line.

You should notice that each printed number should be non-negative and less than $95542721$ .