Description

Crawl, crawl~ crawl, crawl~~ The caterpillar crawled under a small "Maojing Tree" and found that it bore its favorite maomao fruits. The "Maojing Tree" has $N$ nodes and $N-1$ edges. There are no maomao fruits on the nodes; all maomao fruits grow on the edges. This "Maojing Tree" has magical power: it can change the number of maomao fruits on its edges:

• Change k w: Set the number of maomao fruits on the $k$-th edge to $w$.
• Cover u v w: Set the number of maomao fruits on every edge along the path between nodes $u$ and $v$ to $w$.
• Add u v w: Increase by $w$ the number of maomao fruits on every edge along the path between nodes $u$ and $v$.

Since the caterpillar is greedy, it will ask the following query:

• Max u v: Query the maximum number of maomao fruits among all edges along the path between nodes $u$ and $v$.

Input Format

The first line contains a positive integer $N$.

The next $N-1$ lines each contain three positive integers $U_i$, $V_i$, and $W_i$. The $(i+1)$-th line describes the $i$-th edge: it connects nodes $U_i$ and $V_i$, and there are $W_i$ maomao fruits on that edge.

Then follow the operations and queries, one per line, terminated by a single line Stop.

Output Format

For each Max query, output its answer on a separate line.

4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop

9
16

Hint

For all testdata, $1 \le N \le 10^5$, and the total number of operations and queries does not exceed $10^5$.

It is guaranteed that at any time, the number of maomao fruits on every edge does not exceed $10^9$.

Translated by ChatGPT 5