Description

一棵有$N$ 个节点的树，节点编号为$1$..$N$。

每个节点都有一个权值。

有$4$种类型的操作：

①$1$ $x$ $y$ $a$ $b$ ，从树中删除一条边$x$ -$y$ ，然后添加一条新边$a$ $-$$b$ ；确保在添加新边后它仍然构成树；

②$2$ $a$ $b$ $w$ ，将节点$a$ 和$b$ 路径上所有节点$（$包括$a$ 和$b$ $）$的权值都修改为$w$ ；

③$3$ $a$ $b$ $d$ ，将节点$a$ 和$b$ $（$包括$a$ 和$b$ $）$路径上所有节点的权值都增加$d$ ；

④$4$ $a$ $b$ ，查询节点$a$ 和$b$ $（$包括$a$ 和$b$ $）$路径上的第$2$大权值，以及该权值在路径上出现的次数。

注意：这里是严格的第$2$大权值。{$3$, $5$, $2$, $5$, $3$}的严格第$2$大权值是$3$。

Format

Input

第$1$行包含一个整数$T$ $（$$T$ $≤$$3$$）$，表示测试用例数。

每个测试用例的第$1$行都包含两个整数$N$ 和$M$ $（$$N$、$M$ $≤$$10^5$ $）$，表示节点数和操作数；

第$2$行包含$N$ 个整数，表示节点的权值；

接下来的$N$ -$1$行，每行都包含两个整数$a$ 和$b$ ，表示在节点$a$ 和$b$ 之间有一条边；

最后$M$行描述操作。其中，$1$$≤$$x$ , $y$ , $a$ , $b$ $≤$$N$ ，|$w$ |$≤$$10^4$ ，|$d$ |$≤$$10^4$。

Output

对每个测试用例，都先单行输出“$Case$ #$x$:”（$x$表示测试用例编号）；

对每个查询操作都输出两个值，即第$2$大权值及其出现的次数。若路径上所有节点的权值都相同，则输出“$ALL$ $SAME$”。

Samples

2
3 2
1 1 2
1 2
1 3
4 1 2
4 2 3
7 7
5 3 2 1 7 3 6
1 2
1 3
3 4
3 5
4 6
4 7
4 2 6
3 4 5 -1
4 5 7
1 3 4 2 4
4 3 6
2 3 6 5
4 3 6

Case #1:
ALL SAME
1 2
Case #2:
3 2
1 1
3 2
ALL SAME

来源

HDU5002