Background

Problem Description

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

1. 1 x y: Add an edge between $x$ and $y$. It is guaranteed that this edge does not exist before.
2. 2 x y: Delete the edge between $x$ and $y$. It is guaranteed that this edge exists before.
3. 3 x y: Modify $a_x$ to $y$.
4. 4 x: Suppose the graph is divided into $k$ connected components $C_1, C_2, \cdots, C_k$. Compute $\sum_{i=1}^k \prod_{j\in C_i}(a_j+x) \bmod u^v$.

Input Format

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

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

The next $q$ lines each describe one operation.

Output Format

Output several lines. Each line contains one integer, the answer for each type $4$ operation.

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

7
1
3
3

Hint

Idea: I forgot the source. Please ask the original problem setter by private message on QQ.

Sample 2

See the attachments ex_c2.in and ex_c2.ans. This sample satisfies Subtask $1$.

Sample 3

See the attachments ex_c3.in and ex_c3.ans. This sample satisfies Subtask $2$.

Sample 4

See the attachments ex_c4.in and ex_c4.ans. This sample satisfies Subtask $6$.

Limits and Notes

This problem uses bundled tests.

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 type $3$ operations, $y$, and in type $4$ operations, $x$, are both non-negative integers less than $10^4$.

Translated by ChatGPT 5