Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:1024 MB
Statistics

题⽬描述

塑料内存条是⼀种可以存储数的集合的存储介质。

你有 $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)}:$ 无特殊性质。

大样例