题目描述

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$ 行，是进行下面的操作：

• 1 u v 如果城市 $u$ 和城市 $v$ 已经无直接连接的道路，则忽略这个操作，否则删除 $u,v$ 之间的道路。
• 2 u v 如果城市 $u$ 和城市 $v$ 联通那么忽略。否则在 $u,v$ 之间添加一条道路。
• 3 u v d 如果城市 $u$ 和城市 $v$ 不连通，那么忽略。否则将城市 $u$ 到城市 $v$ 的路径中所有城市（包括 $u$ 和 $v$）的美丽度都增加 $d$。
• 4 u v 询问 $E(u,v)$ 的值。

输出格式

对于操作 4，输出答案，一个经过化简的分数 $\frac{p}{q}$。如果 $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

提示

对于所有数据满足 $1\le N\le 50000,1\le M\le 50000,1\le a_i\le 10^6,1\le D\le 100,1\le u,v\le N$。