城市旅行

题目描述

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，输出答案，一个经过化简的分数p/q。如果u和v不连通输出-1。

样例 #1

样例输入 #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

样例输出 #1

16/3
6/1

提示

对于所有数据满足 1<=N<=50,000 1<=M<=50,000 1<=a_i<=10^6 1<=D<=100 1<=U,V<=N