Description

给定$n$ 个节点及每个节点的权值，节点编号为$1$～$n$ ，处理$m$ 种操作。

操作格式： ①$0$ $x$ $y$ ，查询$x$ 到$y$ 路径上点的权值的$x$$o$$r$和，保证$x$ 到$y$ 是连通的；

②$1$ $x$ $y$ ，连接$x$ 到$y$ ，若$x$到$y$ 已经连通，则无须连接；

③$2$ $x$ $y$ ，删除边$($$x$ , $y$ $)$，不保证边$($$x$, $y$ $)$存在；

④$3$ $x$ $y$ ，将节点$x$ 的权值变成$y$ 。

Format

Input

第$1$行包含两个整数$n$ 和$m$ ，表示节点数和操作数，$1$$≤$$n$$≤$$10^5$ ，$1$$≤$$m$ $≤$$3$×$10^5$ ；

接下来的$n$ 行，每行都包含一个[$1$, $10^9$ ]的整数，代表节点的权值；最后的$m$ 行，每行都包含$3$个整数，表示一种操作。

Output

对每个查询操作，都单行输出一个整数，表示$x$ 到$y$ 路径。

Samples

3 3
1
2
3
1 1 2
0 1 2
0 1 1

3
1