CF1628E.Groceries in Meteor Town

Mihai lives in a town where meteor storms are a common problem. It's annoying, because Mihai has to buy groceries sometimes, and getting hit by meteors isn't fun. Therefore, we ask you to find the most dangerous way to buy groceries so that we can trick him to go there.

The town has $n$ buildings numbered from $1$ to $n$. Some buildings have roads between them, and there is exactly $1$ simple path from any building to any other building. Each road has a certain meteor danger level. The buildings all have grocery stores, but Mihai only cares about the open ones, of course. Initially, all the grocery stores are closed.

You are given $q$ queries of three types:

1. Given the integers $l$ and $r$, the buildings numbered from $l$ to $r$ open their grocery stores (nothing happens to buildings in the range that already have an open grocery store).
2. Given the integers $l$ and $r$, the buildings numbered from $l$ to $r$ close their grocery stores (nothing happens to buildings in the range that didn't have an open grocery store).
3. Given the integer $x$, find the maximum meteor danger level on the simple path from $x$ to any open grocery store, or $-1$ if there is no edge on any simple path to an open store.

米海住在一个经常发生流星风暴的小镇。这很烦人，因为米海有时需要去购买杂货，而被流星击中可不好玩。因此，我们请你找出购买杂货最危险的路径，以便我们能诱骗他前往那里。

小镇共有 $n$ 座建筑，编号从 $1$ 到 $n$。部分建筑之间有道路相连，且任意两座建筑之间恰好存在一条简单路径。每条道路都有一个特定的流星危险等级。所有建筑均设有杂货店，但米海只关心那些当前营业中的杂货店（当然）。初始时，所有杂货店均处于关闭状态。

你将收到 $q$ 个查询，共三种类型：

1. 给定整数 $l$ 和 $r$，将编号在区间 $[l, r]$ 内的所有建筑的杂货店设为营业状态（对于该区间内已处于营业状态的杂货店，不作任何操作）；
2. 给定整数 $l$ 和 $r$，将编号在区间 $[l, r]$ 内的所有建筑的杂货店设为关闭状态（对于该区间内原本未营业的杂货店，不作任何操作）；
3. 给定整数 $x$，求从建筑 $x$ 到任意一家营业中杂货店的简单路径上，所经过道路的最大流星危险等级；若不存在通往任何营业中杂货店的简单路径（即：不存在连接 $x$ 与任一营业中杂货店的路径），则输出 $-1$。

The first line contains the two integers $n$ and $q$ ($2 \le n, q \le 3\cdot 10^5$).

Then follows $n - 1$ lines, the $i$-th of which containing the integers $u_i$, $v_i$, and $w_i$ ($1 \le u_i, v_i \le n, \enspace 1 \le w_i \le 10^9$) meaning there is two way road between building $u_i$ and $v_i$ with meteor danger level $w_i$.

It is guaranteed that the given edges form a tree.

Then follows $q$ lines, the $j$-th of which begin with the integer $t_j$ ($1 \le t_j \le 3$), meaning the $j$-th query is of the $t_j$-th type.

If $t_j$ is $1$ or $2$ the rest of the line contains the integers $l_j$ and $r_j$ ($1 \le l_j \le r_j \le n$).

If $t_j$ is $3$ the rest of the line contains the integer $x_j$ ($1 \le x_j \le n$).

第一行包含两个整数 $n$ 和 $q$（$2 \le n, q \le 3\cdot 10^5$）。

接下来是 $n - 1$ 行，其中第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $w_i$（$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^9$），表示建筑物 $u_i$ 与 $v_i$ 之间存在一条双向道路，其陨石危险等级为 $w_i$。

保证所给的边构成一棵树。

随后是 $q$ 行，其中第 $j$ 行以整数 $t_j$（$1 \le t_j \le 3$）开头，表示第 $j$ 个查询属于第 $t_j$ 类型。

若 $t_j = 1$ 或 $t_j = 2$，则该行其余部分包含两个整数 $l_j$ 和 $r_j$（$1 \le l_j \le r_j \le n$）。

若 $t_j = 3$，则该行其余部分包含一个整数 $x_j$（$1 \le x_j \le n$）。

For each query of the $3$rd type ($t_j = 3$), output the maximum meteor danger level that is on some edge on the simple path from $x_j$ to some open store, or $-1$ if there is no such edge.

对于每个第 3 类查询（$t_j = 3$），输出从 $x_j$ 到某个开放商店的简单路径上所有边中最大的流星危险等级；若不存在这样的边，则输出 $-1$。

This is an illustration of the town given in the sample input.

In the first query, there are no open stores, so obviously there are no edges on the simple path from $1$ to any open store, so the answer is $-1$.

After the second and third queries, the set of open stores is ${1}$. The simple path from $1$ to $1$ has no edges, so the answer for the $3$rd query is $-1$.

After the fourth query, there are no open stores.

After the fifth and sixth queries, the set of open stores is ${5, 6}$. In the sixth query, there are two paths from $x_j = 4$ to some open grocery store: $4$ to $5$ and $4$ to $6$. The biggest meteor danger is found on the edge from $4$ to $6$, so the answer for the $6$th query is $4$. This path is marked with red in the illustration.

After the rest of the queries, the set of open stores is ${5}$. In the eighth query, the only path from $x_j = 4$ to an open store is from $4$ to $5$, and the maximum weight on that path is $3$. This path is marked with green in the illustration.

In the ninth query, the only path from $x_j = 1$ to an open store is from $1$ to $5$, and the maximum weight on that path is $5$. This path is marked with blue in the illustration.

这是样例输入中所给城镇的示意图。

在第一个查询中，没有开放的商店，因此从节点 $1$ 到任意开放商店的简单路径上显然不存在边，故答案为 $-1$。

在第二和第三个查询之后，开放商店的集合为 $\{1\}$。从节点 $1$ 到节点 $1$ 的简单路径不含任何边，因此第三个查询的答案为 $-1$。

在第四个查询之后，没有开放的商店。

在第五和第六个查询之后，开放商店的集合为 $\{5, 6\}$。在第六个查询中，从 $x_j = 4$ 到某个开放杂货店存在两条路径：$4 \to 5$ 和 $4 \to 6$。其中边 $4 \to 6$ 上的流星危险值最大，因此第六个查询的答案为 $4$。该路径在示意图中以红色标出。

在后续所有查询中，开放商店的集合均为 $\{5\}$。在第八个查询中，从 $x_j = 4$ 到开放商店的唯一路径为 $4 \to 5$，该路径上的最大边权为 $3$。该路径在示意图中以绿色标出。

在第九个查询中，从 $x_j = 1$ 到开放商店的唯一路径为 $1 \to 5$，该路径上的最大边权为 $5$。该路径在示意图中以蓝色标出。