P4681 [THUSC 2015] 平方运算

小 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

对于每一个询问，输出答案。

$1\leq N,M\leq 10^{5}$。 $$ \begin{aligned}P\in \{233,2332,5,8192,23,45,37,4185,5850,2975,2542,\\2015,2003,2010,4593,4562, 1034,5831,9905,9977\} \end{aligned} $$