Problem Description

Xiao H is a hardworking middle school student. His dream is to enter his favorite university to study computer science. To achieve this goal, he has been seriously studying the basic knowledge of informatics competitions since childhood.

Today, Xiao H learned the square operation. To check whether he has mastered it well, Xiao H decided to make himself a problem. Xiao H has a sequence of length $N$, ${X_1,X_2,\cdots,X_N}$. From time to time, Xiao H takes a continuous interval $[l,r]$ from the sequence and changes each number in it to the result of squaring its original value modulo $P$, where $P$ is a given number. To verify whether his computation is correct, Xiao H also wants to know, from time to time, what the sum of all numbers in a continuous interval $[l,r]$ of the sequence is.

However, Xiao H does not have the standard answers now. So, he asks you for help and hopes you can write a program to compute the sum of the numbers in the interval each time he asks.

Input Format

The first line contains three integers $N,M,P$, where $M$ is the number of operations, and the meanings of $N$ and $P$ are as described in the statement.

The next line contains $N$ positive integers, $X_1,X_2,X_3,\cdots,X_N$, where $X_i<P$.

Then follow $M$ lines. Each line is in the format $1\;l\;r$ or $2\;l\;r$. $1$ means modifying the value of each element, and $2$ means querying the interval sum.

Output Format

For each query, output the answer.

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

Hint

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

Translated by ChatGPT 5