Caterpillar's Magic Tree

In this problem, you are given a tree with (N) nodes and (N-1) edges. Each edge (branch) has an associated number of hairy fruits. There are four types of operations you need to process on the tree:\

1. (\mathbf{Change; k; w}): Change the fruit count on the (k)th edge to (w).\
2. (\mathbf{Cover; u; v; w}): Set the fruit count on every edge in the unique path between nodes (u) and (v) to (w).\
3. (\mathbf{Add; u; v; w}): Increase the fruit count on every edge in the path between nodes (u) and (v) by (w).\
4. (\mathbf{Max; u; v}): Query the maximum fruit count among the edges in the path between nodes (u) and (v).\

The tree is undirected. The initial state of the tree is provided as input, and the operations may modify the state. For every (Max) operation, you should output the maximum fruit count along the specified path.

inputFormat

The input begins with a line containing two integers (N) and (M), where (N) is the number of nodes and (M) is the number of operations.\ The next (N-1) lines each contain three integers (u), (v), and (w): an edge between nodes (u) and (v) with an initial fruit count of (w). The edges are numbered from 1 to (N-1) in the order of appearance.\ Then, (M) lines follow, each representing an operation in one of the following formats: \n• Change k w \n• Cover u v w \n• Add u v w \n• Max u v

outputFormat

For each Max u v query, output a single line containing the maximum fruit count on the branches along the unique path between nodes (u) and (v).

sample

5 5
1 2 5
1 3 3
2 4 4
2 5 6
Max 4 5
Add 3 4 2
Max 3 4
Cover 1 2 1
Max 3 4

6
7
6