Note: this problem requires Euler's theorem, which by the IOI 2023 Syllabus is Outside of Focus. Necessary information regarding that theorem and modular arithemetic are given in the paragraph below.

You a given a sequence ~a_1,\ldots,a_n~. You are also given a constant ~b~. You need to support the following operations:

• 0 l r: For each ~i~ in ~[l,r]~, update ~a_i~ to ~b^{a_i}~.
• 1 l r: find the sum of the subinterval ~a_l,\ldots,a_r~. That is to say, you need to output $$\displaystyle \sum_{i=l}^r a_i.$$ Since the answer might be large, you only need to output the result modulo ~m~.

Properties of numbers modulo ~m~

The greatest common divisor of two positive integers ~a~ and ~b~ is the maximum integer ~g~ that divides both ~a~ and ~b~. ~a~ and ~b~ are coprime if their greatest common divisor is ~1~.

Let ~\varphi(n)~ denote the number of integers in ~1,\ldots,n~ that are coprime to ~n~. You can compute ~\varphi(n)~ using the following relation: $$\displaystyle \varphi(n) = n\prod_{p | n}(1 - \frac{1}{p})$$ Here, the product is over the distinct prime numbers dividing ~n~.

Alternatively, suppose the prime factorization of ~n~ is given by $$\displaystyle n = p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r}$$ where ~k_i \geq 1~, then $$\displaystyle \varphi(n) = p_1^{k_1 - 1}(p_1 - 1)p_2^{k_2-1}(p_2-1) \cdots p_r^{k_r-1}(p_r-1).$$

The Extended Euler's Theorem asserts the following relation for ~b^a \bmod m~.

• If ~a < \varphi(m)~, then nothing interesting can be said: ~b^a \equiv b^a \bmod m~.
• If ~a \geq \varphi(m)~, we have ~b^a \equiv b^{(a \bmod \varphi(m)) + \varphi(m)} \bmod m~.

Note that this holds even when ~b~ and ~m~ are not coprime to each other.

Input Specification

The first line of the input contains four integers ~n,q,m,b~. ~n~ stands for the length of the sequence, ~q~ is the number of operations, ~m~ is the modulus, and ~b~ is the base.

The next line contains ~n~ integers denoting the inital sequence ~a_1,\ldots,a_n~.

In the following ~q~ lines, each line consists of a query using the format specified above.

Output Specification

For each query of the form 1 l r, output a line with an integer denoting the sum (~\bmod m~).

Sample Input

4 5 20 3
2 0 2 3
0 1 4
1 3 4
0 1 4
1 1 3
1 2 4

Sample Output

16
9
13

Explanation of Sample 1

Initially, ~a = (2,0,2,3)~.

After the first operation, ~a = (3^2, 3^0, 3^2, 3^3) = (9,1,9,27)~.

After the third operation, ~a = (3^9, 3^1, 3^9, 3^{27})~. Thus, ~a \bmod 20 = (3,3,3,7)~.

Sample Input 2

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

Sample Output 2

0

Explanation of Sample 2

Initially ~a = (0, 1, 0)~. The three operations on it takes it to ~(1, 2, 1)~, ~(2, 4, 2)~, and ~(4, 16, 4)~ respectively.

Constraints

For all test cases, ~1 \leq n \leq 2 \times 10^5, 3 \leq m \leq 10^7, q \leq 5 \times 10^5~, ~2 \leq b < m~. For all ~a_i~, initially ~0 \leq a_i < m~. For all queries, we have ~1 \leq l \leq r \leq n~.

• Subtask 1 (10 points): ~m = 3, n \leq 100, q \leq 100~.
• Subtask 2 (20 points): ~n \leq 100, q \leq 100~. Depends on Subtask 1.
• Subtask 3 (10 points): ~m \leq 10~, for all queries of form 0 l r, ~l = r~, and each array element will only be modified at most once. Notice we only guarantee we modify one value at a time, we might still ask for the sum over an interval.
• Subtask 4 (10 points): ~m \leq 10~. Depends on Subtask 1,3.
• Subtask 5 (20 points): ~m \leq 1000~. Depends on Subtask 1,3,4.
• Subtask 6 (30 points): No additional constraints. Depends on all previous subtasks.
• Warning: ~m~ is not always a prime.