题目描述

小 A 和 Sharon 从小就是好朋友，他们总喜欢在院子里玩耍。渐渐地，他们成为了高中生，如今他们已各奔东西。某天，小 A 和 Sharon 恰在 W 国相遇，我们的问题从此展开。

W 国地大物博，由 $n$ 座城市组成，共有 $n-1$ 条双向道路连接其中的两座城市，且任意两座城市都可以相互到达。风景秀美的 W 国吸引了无数慕名而来的游客，根据游客对每座城市的打分，我们定义第 $i$ 座城市的美丽度为 $a_i$。一次从城市 $x$ 到城市 $y$ 的旅行，所获得的的愉悦指数为从城市 $x$ 到城市 $y$ 所有城市的美丽度之和（包括 $x$ 和 $y$），我们定义这个值为 $H(x,y)$。现在小 A 在城市 $X$，Sharon 在城市 $Y$，他们想知道如果在城市 $X$ 到城市 $Y$ 之间的所有城市中任意选择两座城市 $x$ 和 $y$（$x$ 可以等于 $y$），那么 $H(x,y)$ 的期望值是多少，我们记这个期望值为 $E(X,Y)$。

当然，处在信息时代的我们，城市之间的交通状况飘忽不定，因此我们不能排除某些时刻某些道路将无法通行，某些时刻会突然添加新的道路。以及游客们审美观的改变，某些城市的美丽度也会发现变化。作为 W 国负责旅游行业的 T 君，他要求你来写一个程序来模拟上面的所有过程，你的程序需要支持：

输入格式

第一行两个整数 $n,m$，分别表示城市个数以及操作个数。

接下来一行共 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$，表示初始时城市 $u$ 和城市 $v$ 之间有一条道路相连。

接下来 $m$ 行，每行 $3$ 或 $4$ 个整数为上表所述的 $4$ 种操作之一。

输出格式

对于每个操作 $4$，输出一个既约分数表示 $E(u,v)$ 的值，输出格式为 分子/分母 （要求分子与分母互质），特别地，若城市 $u$ 和城市 $v$ 不连通，则输出一个整数 -1。

4 5
1 3 2 5
1 2
1 3
2 4
4 2 4
1 2 4
2 3 4
3 1 4 1
4 1 4

16/3
6/1

数据规模与约定

对于 $100\%$ 的数据，$1\le n,m\le 5\times 10^4$，$1\le a_i\le 10^6$，$1\le d\le 100$，$1\le u,v\le n$。