本题没有可用的提交语言。

题目背景

题目描述

星野加奈给你一个 $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$ 操作的答案。

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

提示

Idea：忘记来源了，请当时的出题人 qq 私信我

样例二

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

样例三

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

样例四

见附件中的 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$		$/$
$2$	$10$	$10^5$		对所有 $4$ 操作，$x=0$。
$3$	$15$			$v=1$
$4$				对所有 $4$ 操作，$x$ 是 $u$ 的倍数。
$5$				没有 $2,3$ 操作。
$6$	$25$			$/$