← 返回题目列表

Codeforces · 311/D

D. 区间立方

中文机器翻译题面 查看原题

在学习计算几何时,Tiny 正在同时学习一种称为线段树或区间树的有用数据结构。还没等他明白,一个奇怪的问题就出现了:

给定一个整数序列 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 中的每个元素 x 变为 x3。换句话说,应用赋值 al = al3, al + 1 = al + 13, ..., ar = ar3。

对于类型 1 的每个查询,输出其答案。

小小自己肯定无法解决这个问题,所以他向你寻求帮助。此外,Tiny还是一位顶级情人。他告诉你,因为答案可能太大,所以你应该只输出它模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。

示例

输入 #1

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

输出 #1

14
224
2215492