Problem Description

Xiao H is a diligent middle school student with the dream of studying computer science at his dream university. To achieve this goal, he has been diligently learning the basics of competitive programming since he was young.

Today, Xiao H learned about square operations. To test his mastery of this concept, he decided to create a problem for himself. Xiao H has a sequence of length $N$, denoted as ${X_1, X_2, \cdots, X_N}$. He will occasionally select a continuous interval $[l, r]$ from this sequence and modify each number within this interval to its square modulo $P$, where $P$ is a given number. To verify the correctness of his calculations, Xiao H also wants to know the sum of all numbers in a certain continuous interval $[l, r]$ from time to time.

However, Xiao H does not have the standard answers. Therefore, he seeks your help, hoping you can write a program to calculate the sum of the numbers in the intervals he wants to know each time.

Input Format

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

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

The following $M$ lines of input each contain a format like $1\;l\;r$ or $2\;l\;r$, where $1$ indicates modifying the value of each element, and $2$ indicates querying the interval sum.

Output Format

For each query, output the answer.

Sample Input and Output

Input Sample #1

1 3 233
1 
2 1 1
1 1 1
2 1 1

Output Sample #1

1
1

Input Sample #2

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

Output Sample #2

10
8

Notes

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

见题面 Input 部分

见题面 Output 部分