如今，Dreamgrid 王国正遭受着全国性大流行的困扰。幸运的是，Baobao 总统正与疾病控制中心（CDC）高效合作，他们正尽最大努力控制局势。

作为 CDC 的负责人，你需要同时更新疫情状况，并回答来自 Baobao 总统本人以及世界各地新闻机构记者的询问。

具体来说，我们将这个国家看作一个包含 $n$ 个节点的图，节点代表城市。由于疫情严重，除了 $n-1$ 条保持国家连通的道路外，其余大部分道路和高速公路均已关闭。我们定义每个城市 $x$ 的 $F(x)$ 为当地疫情的严重程度。现在你需要处理以下三类事件/查询：

1. 城市 $x$ 发生了另一次疫情爆发，严重程度值为 $w$。对于每个城市 $y$，$F(y)$ 将增加 $w - \text{dist}(x, y)$，其中 $\text{dist}(x, y)$ 是从 $x$ 到 $y$ 的路径上的边数。
2. 将城市 $x$ 的 $F(x)$ 更新为 $\min(F(x), 0)$，这意味着在政府和医疗部门的努力下，城市 $x$ 的情况得到了改善。
3. 查询城市 $x$ 的严重程度值 $F(x)$。

每个城市的严重程度值 $F$ 初始均为 0。此外，$F(x)$ 在某些时刻可能为负值，我们无需对其进行调整。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试数据的组数。

对于每组测试数据，第一行包含两个整数 $n, m$ ($1 \le n, m \le 5 \times 10^4$)，分别表示城市数量和事件/查询的数量。接下来的 $n-1$ 行描述了该国的所有路径，每行包含两个整数 $x, y$ ($1 \le x, y \le n$)，表示城市 $x$ 和 $y$ 之间的一条道路。接下来的 $m$ 行描述了所有事件，每行以一个整数 $opt$ ($1 \le opt \le 3$) 开头，如果 $opt$ 为：

1. 该行会有两个整数 $x, w$ ($1 \le x \le n, 0 \le w \le 10000$)。这对应上述描述中的事件 1。
2. 该行会有一个整数 $x$ ($1 \le x \le n$)。这对应事件 2。
3. 该行会有一个整数 $x$ ($1 \le x \le n$)。这对应你需要回答的查询。

输出格式

对于每个查询，输出一行一个整数。

样例

样例输入 1

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

样例输出 1

3
9
6