题⽬描述
塑料内存条是⼀种可以存储数的集合的存储介质。
你有 $n$ 根塑料内存条,初始时第 $i$ 根内存条存储的集合为 ${c_i}$。
Isla 希望你执⾏ $m$ 次操作,每次操作为以下类型之⼀:
1 x y
:在内存条 $x$ 存储的集合中插⼊数 $y$。
2 x y
:将内存条 $y$ 存储的集合中所有数插⼊到内存条 $x$ 的集合中,并丢弃内存条 $y$。保证 $x\ne y$,且 $y$ 不会在以后的操作中出现。
3 x y
:对于内存条 $x,y$ 存储的集合 $S_x,S_y$,询问 $(\sum\limits_{v\in S_x\cap S_y}v^a)^b$。其中 $a,b$ 为⼀开始给定的常数。保证 $x\ne y$。
。
输⼊格式
第 1 ⾏ 4 个⾮负整数 $n,m,a,b$。
第 2 ⾏ $n$ 个整数描述序列 $c_{1\dots n}$。
接下来 $n$ ⾏,第 $i$ ⾏ 3 个正整数 $op_i,x_i,y_i$,表⽰⼀次操作。
输出格式
对于每个类型 3 的操作,输出⼀个⾮负整数,表⽰答案。
样例输入
5 7 1 1
2 3 5 2 5
2 3 4
1 2 5
2 5 3
3 5 1
2 2 1
1 5 1
3 5 2
样例输出
2
7
数据范围
对于所有数据,$2\le n\le 2\times 10^5,1\le m\le 4\times 10^5,0\le a,b\le 1,1\le x_i,y_i,c_i\le n$。
$\text{subtask1(10pts)}: n\le 1000,m\le 2000$
$\text{subtask2(15pts)}: n\le 50000,m\le 100000,a=0,b=1$
$\text{subtask3(25pts)}: a=b=0$
$\text{subtask4(20pts)}: n\le 50000,m\le 100000$
$\text{subtask2(30pts)}:$ 无特殊性质。