[THUSC2015] 平方运算
题目描述
小 H 是一位勤奋的中学生,他的理想是进入自己心仪的大学学习计算机专业。为了实现这一目标。他从小就开始认真学习信息学竞赛的基础知识。
今天,小 H 学习了平方运算。为了检验自己是否熟练掌握了平方运算,小 H 决定给自己出一道题。小 H 有一个长度为 $N$ 的序列 ${X_1,X_2,\cdots,X_N}$。小 H 会时不时地取出 列中的一段连续区间 $[l,r]$,并将其中的每一个数改为原数值的平方对 $P$ 取模的结果,其中 $P$ 为某个给定的数。为了检验自己的运算是否正确,小 $H$ 还会时不时地想要知道序列中某一段连续区间 $[l,r]$ 内所有数的和是多少。
但是,小 H 现在并没有标准答案。所以,他向你求助,希望你编写一个程序,帮他计算出每次想要知道的区间内的数的和。
输入输出格式
输入格式
输入第一行包含三个整数 $N,M,P$,$M$ 表示操作组数,$N,P$ 含义见题目描述;
接下来一行,包含 $N$ 个正整数,为 $X_1,X_2,X_3,\cdots,X_N$,$X_i<P$;
接下来共 $M$ 行输入,每行格式形如 $1\;l\;r$ 或 $2\;l\;r$,$1$ 表示修改每个元素的值,$2$ 表示询问区间和。
输出格式
对于每一个询问,输出答案。
输入输出样例
输入样例 #1
1 3 233
1
2 1 1
1 1 1
2 1 1
输出样例 #1
1
1
输入样例 #2
4 3 5
1 2 3 4
2 1 4
1 2 4
2 2 3
输出样例 #2
10
8
说明
$1\leq N,M\leq 10^{5}$。
$P\in \{233,2332,5,8192,23,45,37,4185,5850,2975,2542,2015,2003,2010,4593,4562, 1034,5831,9905,9977\}$。