题目描述

现有一个长度为 $n$ 的序列 $\{X_1,X_2,\dots,X_n\}$，要求支持两种操作：

1. $\texttt{0 l r}$：对于 $i \in [l,r]$，$X_i \gets X_i^2 \mod p$。
2. $\texttt{1 l r}$：询问 $\sum_{i=l}^r X_i$。

输入格式

第一行有三个整数 $n,m,p$，分别代表序列的长度、平方操作与询问操作的总次数以及在平方操作中所要模的数。

接下来一行 $n$ 个数代表一开始的序列 $\{X_1,X_2,\dots,X_n\}$。

接下来 $m$ 行，每行三个整数 $op,l,r$。其中 $op$ 代表本次操作的类型。若 $op=0$，代表这是一次平方操作，平方的区间为 $[l,r]$；如果 $op=1$，代表这是一次询问操作，询问的区间为 $[l,r]$。

输出格式

对于每次的询问操作，输出一行代表这段区间内数的总和。

注意：答案没有对任何数取模。

3 3 11
1 2 3
1 1 3
0 1 3
1 1 3

6
14

提示

对于 $100\%$ 的数据，$X_i \in [0,p),~l,r \in [1,n]$.

$n,m,p$ 的范围如下：

题目来源

鸣谢佚名上传