Little H is a diligent middle school student whose dream is to enter his favorite university to study computer science. To achieve this goal, he has been studying the basics of informatics competitions since he was young.

Today, Little H learned about the square operation. To test whether he has mastered it, he decided to create a problem for himself. Little H has a sequence of length $N$, $\{X_1, X_2, \dots, X_N\}$. Little H will occasionally take a continuous interval $[l, r]$ from the sequence and change each number in it to the result of its square modulo $p$, that is: $$\forall i \in [l, r], X_i \leftarrow (X_i \times X_i) \bmod p$$ where $p$ is a given number. To check if his calculations are correct, Little H also wants to know the sum of all numbers in a continuous interval $[l, r]$ of the sequence from time to time.

However, Little H does not have the standard answers now. Therefore, he asks for your help, hoping you can write a program to help him calculate the sum of the numbers in the interval he wants to know each time.

Input

The first line contains three integers $N, M, p$, representing the length of the sequence, the total number of square operations and query operations, and the modulus used in the square operation, respectively.

The next line contains $N$ integers representing the initial sequence $\{X_1, X_2, \dots, X_N\}$.

The next $M$ lines each contain three integers $op, l, r$. Here $op$ represents the type of operation. If $op = 0$, it represents a square operation on the interval $[l, r]$; if $op = 1$, it represents a query operation on the interval $[l, r]$.

Output

For each query operation, output one line representing the sum of the numbers in that interval. Note: The answer is not taken modulo any number.

Constraints

For 100% of the data, $\forall i, X_i \in [0, p)$, $l, r \in [1, N]$. The ranges of $N, M, p$ are detailed in the table below:

Examples

Input 1

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

Output 1

6
14

Input 2

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

Output 2

3
2