U313600 萨妃的游戏

众所周知，$Cloud$ 是 $Sephiroth$ 的杰诺瓦思念体，总是在 $reunion$ 的道路上，追寻着 $Sephiroth$ 。 一天，$Cloud$ 在陆行鸟牧场得知了 $Sephiroth$ 在遗忘之都，于是他骑着陆行鸟和 $Tifa$ 前往遗忘之都。

在陆行鸟牧场到遗忘之都的道路上有一个迷宫。 迷宫可以视为一个 $N$ 个房间，$M$ 条边的联通无向图，$Sephiroth$ 在迷宫的房间中留下了魔力值不等的魔晶石，第 $i$ 个房间的魔晶石的魔力值为 $a_i$ 。 为了打败 $Sephiroth$ ，他们想要获得尽可能高的魔力值。他们已经得到的迷宫的地图，他们想知道从迷宫的一个房间到另一个房间经过的**所有的路径**能获得的**魔力值之和**。 $Sephiroth$ 为了调戏爱妻 $Cloud$ ,会动用黑魔法将迷宫的一个房间到另一个房间经过的**所有的路径**上经过的房间的魔晶石的魔力值增加 $w$ 。 若多条路径经过了同一个房间，魔力值只**计算或增加一次**。 其中，一条合法路径的定义为：**这条路径不经过同一条边两次**。

第一行：两个用空格分开的整数：$N$ , $M$。 接下来一行 $N$ 个数表示每个房间的魔晶石的魔力值 $a_i$ 。 接下来 $M$ 行，每行两个整数 $x,y$ 表示第 $x$ 和第 $y$ 个房间之间有一条边。 接下来一行一个整数 $Q$ 代表操作次数。 接下来 $Q$ 行，首先有一个整数 $opt$ 。 如果 $opt=1$ ，接下来有三个整数 $x,y,w$ ，代表 $Sephiroth$ 动用黑魔法将迷宫的房间 $x$ 到房间 $y$ 经过的所有的路径上经过的房间的魔力值增加 $w$ 。 如果 $opt=2$ ，接下来有两个整数 $x,y$ ，代表 $Cloud$ 询问从迷宫的房间 $x$ 到房间 $y$ 经过的所有的路径能获得的总魔力值。 不保证 $x\neq y$ 。

对于每个 $opt=2$ 的操作，输出一行代表对应所经过的所有的路径能获得的总魔力值。

对于 $100\%$ 的数据，$1\leq N ,Q \leq 10^5$，$N\leq M \leq 5\times10^5$，$-10^3\leq w,a_i\leq 10^3$ ，$1\leq x,y\leq N$。