Hoshino Kana gives you an undirected graph with $n$ vertices, initially containing no edges. She also has integers $u, v$ and $a_1, a_2, \dots, a_n$. There are $q$ operations of four types:

1. 1 x y: Add an edge between $x$ and $y$. It is guaranteed that the edge does not exist initially.
2. 2 x y: Remove the edge between $x$ and $y$. It is guaranteed that the edge exists.
3. 3 x y: Update $a_x$ to $y$.
4. 4 x: Let the graph be partitioned into $k$ connected components $C_1, C_2, \dots, C_k$. Calculate $\sum_{i=1}^k \prod_{j\in C_i}(a_j+x) \bmod u^v$.

Input

The first line contains four integers $n, q, u, v$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

The next $q$ lines each describe an operation.

Output

For each type $4$ operation, output the answer on a new line.

Examples

Input 1

5 10 3 2
1 2 3 4 5
4 2
1 1 2
1 3 4
4 0
1 2 3
3 2 5
4 1
2 3 4
1 4 5
4 2

Output 1

7
1
3
3

Example 2

See ex_c2.in and ex_c2.ans in the attachment. This example satisfies subtask $1$.

Example 3

See ex_c3.in and ex_c3.ans in the attachment. This example satisfies subtask $2$.

Example 4

See ex_c4.in and ex_c4.ans in the attachment. This example satisfies subtask $6$.

Subtasks

This problem uses bundled testing.

For $100\%$ of the data, $1\leq n, q\leq 10^5$, $1\leq u\leq 10$, $1\leq v\leq 4$, $0\leq a_i < 10^4$. In operation $3$, $y$ is a non-negative integer less than $10^4$, and in operation $4$, $x$ is a non-negative integer less than $10^4$.