星野加奈给你一个 $n$ 个点的无向图，图初始没有边。他还有整数 $u,v$ 和 $a_1,a_2,\cdots ,a_n$。现在有 $q$ 次操作，操作有四种：

1. 1 x y ：连接 $x,y$ 之间的边，保证边原先不存在。
2. 2 x y ：删除 $x,y$ 之间的边，保证边原先存在。
3. 3 x y ：将 $a_x$ 修改为 $y$ 。
4. 4 x ：设图分为 $C_1,C_2,\cdots ,C_k$ 共 $k$ 个连通块，求出 $\sum_{i=1}^k \prod_{j\in C_i}(a_j+x) \bmod u^v$。

输入格式

第一行四个整数 $n,q,u,v$。

第二行 $n$ 个整数 $a_1,a_2,\cdots , a_n$。

接下来 $q$ 行，每行表示一次操作。

输出格式

若干行，每行一个整数，表示每次 $4$ 操作的答案。

样例数据

样例 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

样例 1 输出

7
1
3
3

样例 2

见附件中的 ex_c2.in 和 ex_c2.ans，此样例满足子任务 $1$。

样例 3

见附件中的 ex_c3.in 和 ex_c3.ans，此样例满足子任务 $2$。

样例 4

见附件中的 ex_c4.in 和 ex_c4.ans，此样例满足子任务 $6$。

子任务

本题采用捆绑测试。

对于 $100\%$ 的数据，满足 $1\leq n,q\leq 10^5,1\leq u\leq 10,1\leq v\leq 4,0\leq a_i < 10^4$，$3$ 操作中 $y$、$4$ 操作中 $x$ 均为小于 $10^4$ 的非负整数。