题目描述

米浴正在上数据结构课！

在数据结构课中，她学习了树的带权重心。

树的带权重心是这么定义的：

设 $a_i (a_i \ge 1)$ 表示 $i$ 的权值。点 $u$ 是树的重心当且仅当删去 $u$ 节点后，剩下的每个联通块的权值和都 $\le \frac{1}{2} \sum a_i$。

现在她的手上有一颗 $n$ 个节点的树，根节点是 1，点 $i$ 的点权为 $a_i$。

她想找到这棵树的带权重心，但是这太简单了。因此，她给自己加了 $q$ 次操作，每次操作有两种可能：

• $1\ u\ v\ w$，表示给所有 $u$ 到 $v$ 路径上的节点的点权增加 $w$
• $2\ u\ w$，表示给所有 $u$ 的子树内的节点的点权增加 $w$

在每次操作后，她都希望找到这棵树的所有带权重心。如果有多个，那么按照编号从小到大的顺序输出。

输入格式

本题有多组数据。

第一行一个正整数 $T (1 \le T \le 10000)$ 表示数据组数

对于每组数据，第一行两个整数 $n, q (1 \le n, q \le 10^5)$

接下来一行 $n$ 个整数，分别是 $a_1, a_2, \ldots, a_n (1 \le a_i \le 10^8)$

接下来 $n-1$ 行，每行两个整数 $u_i, v_i$，表示树上的一条边

接下来 $q$ 行，第 $i$ 行第一个整数是 $op_i \in \{1, 2\}$

• $op_i = 1$，接下来三个整数 $u, v, w (1 \le u, v \le n, w \le 10^8)$
• $op_i = 2$，接下来两个整数 $u, w (1 \le u \le n, w \le 10^8)$

保证 $\sum n, \sum q \le 10^5$，输入的树是一棵树。

输出格式

对于每组数据，输出 $q$ 行，第 $i$ 行输出若干个整数，分别表示经过 $i$ 次操作后树的所有带权重心按照编号从小到大排序后的结果。

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

1 3
1
3

提示

子任务

对于 100% 的数据，均满足

$1 \le T \le 10000, 1 \le \sum n, \sum q \le 10^5, 1 \le a_i, w \le 10^8$

子任务编号	限制条件	分值
1	$\sum n, \sum q \le 1000$	20
2	满足树是一条链	10
3	满足树是菊花图
4	满足树的形态和操作都是均匀随机生成的	20
5	没有额外限制	40