星野加奈给你一个 $n$ 个点的无向图，图初始没有边。他还有整数 $u,v$ 和 $a_1,a_2,\cdots ,a_n$。现在有 $q$ 次操作，操作有四种：
1 x y：连接 $x,y$ 之间的边，保证边原先不存在。2 x y：删除 $x,y$ 之间的边，保证边原先存在。3 x y：将 $a_x$ 修改为 $y$ 。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$ 的非负整数。
| 子任务编号 | 分值 | $n\leq$ | $q\leq$ | 特殊性质 |
|---|---|---|---|---|
| $1$ | $20$ | $5000$ | $5000$ | |
| $2$ | $10$ | $10^5$ | $10^5$ | 对所有 $4$ 操作，$x=0$。 |
| $3$ | $15$ | $v=1$ | ||
| $4$ | $15$ | 对所有 $4$ 操作，$x$ 是 $u$ 的倍数。 | ||
| $5$ | $15$ | 没有 $2,3$ 操作。 | ||
| $6$ | $25$ |