Description

You are given a tree with $n$ nodes, edges have weights, and nodes are numbered $0 \sim n-1$. You need to support five operations. Edges are indexed by their input order from $1$ to $n-1$.

• C i w Change the weight of the $i$-th edge in the input to $w$.
• N u v Negate the weights of all edges on the path between $u$ and $v$.
• SUM u v Query the sum of edge weights on the path between $u$ and $v$.
• MAX u v Query the maximum edge weight on the path between $u$ and $v$.
• MIN u v Query the minimum edge weight on the path between $u$ and $v$.

At any time, all edge weights are within $[-1000, 1000]$.

Input Format

The first line contains a positive integer $n$, the number of nodes. The next $n-1$ lines each contain three integers $u, v, w$, indicating that there is an edge between $u$ and $v$ with weight $w$, describing the tree. Then a line with a positive integer $m$, the number of operations. The next $m$ lines each describe one operation.

Output Format

For each query operation, output one line with one integer representing the answer.

3
0 1 1
1 2 2
8
SUM 0 2
MAX 0 2
N 0 1
SUM 0 2
MIN 0 2
C 1 3
SUM 0 2
MAX 0 2

3
2
1
-1
5
3

Hint

Constraints

For $100\%$ of the testdata, $1 \le n, m \le 2 \times 10^5$.

2020.02.04 Fixed a small error in the testdata. 2020.03.14 Added a set of hack testdata. 2020.11.26 Added a set of hack testdata by @_Leaving.

Translated by ChatGPT 5