Problem Description

Informatik verbindet dich und mich.
Information connects you and me.

Mr. B wishes to maintain an array of length $n$, with indices ranging from $1$ to $n$.

There are $m$ operations, which can be of two types:

• 0 l r indicates replacing each number in the range from the $l$-th to the $r$-th (i.e., $a_l, a_{l+1}, ..., a_r$) with $c^{a_i}$, where $c$ is a constant provided in the input. This means performing the assignment $a_i = c^{a_i}$.

• 1 l r asks for the sum of the numbers from the $l$-th to the $r$-th, and outputs this sum modulo $p$.

Input Format

The first line contains four integers $n, m, p, c$, where the meanings of these integers are as described in the problem.
The next line contains $n$ integers representing the initial values of the array $a$.
The following $m$ lines, each containing three integers, describe the operations. The first integer indicates the type of operation:

• If it is $0$, it denotes a modification operation with parameters $l, r$.
• If it is $1$, it denotes a query operation with parameters $l, r$.

Output Format

For each query operation, output a line containing a single integer, which is the result modulo $p$.

Sample Input and Output

Input Sample #1

4 4 7 2
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3

Output Sample #1

0
3

Input Sample #2

1 40 19910626 2
0
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 1 1

Output Sample #2

1
2
4
16
65536
11418102
18325590
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558
13700558

Notes

Data Range

For $0\%$ of the test points, the input is exactly the same as Sample #1.

For another $10\%$ of the test points, there are no modifications.

For another $20\%$ of the test points, each modification operation only modifies one position (i.e., $l = r$), and each position is modified at most once.

• For another $10\%$ of the test points, $p = 2$.
• For another $10\%$ of the test points, $p = 3$.
• For another $10\%$ of the test points, $p = 4$.
• For another $20\%$ of the test points, $1 \le n, m \le 100$.
• For $100\%$ of the test points, $1 \le n, m \le 5 \times 10^4$, $1 \le p \le 10^8$, $0 < c < p$, $0 \le a_i < p$.

见题面 Input 部分

见题面 Output 部分