Diameter of Homogeneous Connected Components on Trees

You are given an unrooted tree with n nodes and n-1 edges. Each edge has a positive weight. Every node has a color, which can be either black (represented by 1) or white (represented by 2). Initially, all nodes are black.

You need to process m operations. There are two types of operations:

• 1 u: Query the diameter of the connected component (in the tree induced by nodes of the same color) that contains node u. The diameter of a connected component is defined as the maximum distance between any two nodes in that component. If the diameter is 0 (i.e. the connected component contains a single node), output QwQ.
• 2 u v c: Update the color for all nodes on the simple path (chain) from node u to node v (inclusive) to the new color c (either 1 or 2).

Note: All formulae must be in LaTeX format. For instance, the number of nodes is given as $n$, and an edge’s weight is a positive number.

Input Format: The first line contains two integers n and m. The next n-1 lines each contain three integers u, v and w representing an edge between nodes $u$ and $v$ with weight $w$. The following m lines each describe an operation in one of the two forms described above.

Output Format: For each query operation (1 u), output the diameter of the corresponding homogeneous connected component on a new line. If the diameter equals 0, output QwQ instead.

inputFormat

The first line contains two integers n and m.

The next n-1 lines each contain three integers u, v, and w, indicating there is an edge between nodes $u$ and $v$ with weight $w$.

Then, m lines follow, each line representing an operation. An operation is in one of the following two forms:

• 1 u
• 2 u v c

It is guaranteed that $1 \le u,v \le n$ and $c \in \{1,2\}$.

outputFormat

For every query operation (of the form 1 u), output the diameter of the same-color connected component containing node $u$. If the diameter is 0, output QwQ instead.

sample

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

7
2
QwQ