Description

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

Mr. B wants to maintain an array of length $n$, whose indices are the positive integers from $1$ to $n$.

There are $m$ operations, of two types:

• 0 l r means: for each number $a_i$ among the $l$-th to the $r$-th numbers ($a_l,a_{l+1} ...a_r$), replace $a_i$ with $c^{a_i}$, i.e., assign $a_i = c^{a_i}$, where $c$ is a given constant in the input.

• 1 l r asks for the sum of the $l$-th to the $r$-th numbers, i.e., output $\sum_{i=l}^{r} a_i$.

Because the result can be very large, you only need to output the result $\bmod \space p$.

Input Format

The first line contains four integers $n, m, p, c$, whose meanings are given in the problem statement.
The next line contains $n$ integers, the initial values of the array $a$.
The next $m$ lines each contain three integers; the first integer indicates the type of operation.

• If it is 0, this is an update operation with parameters $l, r$.
• If it is 1, this is a query operation with parameters $l, r$.

Output Format

For each query operation, output one line with a single integer: the answer $\bmod \space p$.

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

0
3

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
0 1 1
1 1 1

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

Hint

Constraints

• For $0\%$ of the test points, identical to the sample.
• For another $10\%$ of the test points, there are no updates.
• For another $20\%$ of the test points, each update modifies only one position (i.e., $l = r$), and each position is updated 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$.

Translated by ChatGPT 5