题目描述

小 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 3 233
1 
2 1 1
1 1 1
2 1 1

1
1

4 3 5
1 2 3 4 
2 1 4
1 2 4
2 2 3

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\}$。