CF311D.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 + 13, ..., 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).

在学习计算几何的过程中，Tiny 同时也在学习一种有用的数据结构——线段树（也称区间树）。他刚刚掌握这种数据结构，就遇到了一个奇怪的问题：

给定一个整数序列 $a_1, a_2, ..., a_n$。你需要执行 $q$ 个查询，查询分为两类：

1. 给定两个整数 $l$ 和 $r$（满足 $1 ≤ l ≤ r ≤ n$），求序列中子段 $a_l, a_{l+1}, ..., a_r$ 的所有元素之和；
2. 给定两个整数 $l$ 和 $r$（满足 $1 ≤ l ≤ r ≤ n$），将子段 $a_l, a_{l+1}, ..., a_r$ 中的每个元素 $x$ 替换为 $x^3$。即执行赋值操作：$a_l = a_l^3,\, a_{l+1} = a_{l+1}^3,\, ..., \, a_r = a_r^3$。

对每个类型 1 的查询，请输出对应的答案。

Tiny 自己当然无法解决这个问题，于是向你求助。此外，Tiny 是一位质数爱好者。他告诉你：由于答案可能非常大，你只需输出答案对 $95542721$ 取模的结果（该数是一个质数）。

The first line contains an integer n (1 ≤ n ≤ 105), representing the length of the sequence. The second line contains n space-separated integers _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 109).

The third line contains an integer q (1 ≤ q ≤ 105), 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.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示序列的长度。
第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 10^9$）。

第三行包含一个整数 $q$（$1 \leq q \leq 10^5$），表示查询的数量。随后是 $q$ 行，每行包含三个整数 $t_i$（$1 \leq t_i \leq 2$）、$l_i$、$r_i$（$1 \leq l_i \leq r_i \leq n$），其中 $t_i$ 表示查询类型，$l_i$ 和 $r_i$ 是该查询对应的参数。

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.

对于每个类型为 1 的查询，请每行输出其答案。

请注意：每个输出的数字都应为非负数，且小于 $95542721$。