Tree Query Operations

Given a tree with n nodes, numbered from 0 to n-1, where each edge has an associated weight, you are required to support the following operations:

• C i w: Change the weight of the edge with index i to w.
• N u v: Change the sign of every edge weight on the unique path between nodes u and v (i.e. update each weight w to -w).
• SUM u v: Query the sum of the weights on the path between nodes u and v.
• MAX u v: Query the maximum edge weight on the path between nodes u and v.
• MIN u v: Query the minimum edge weight on the path between nodes u and v.

At any moment, the weight of every edge will always lie within the interval $$[-1000,1000]$$.

inputFormat

The first line contains an integer n representing the number of nodes in the tree.

The next n-1 lines each contain three integers u, v, and w describing an edge between nodes u and v with weight w. The edges are indexed from 0 to n-2 in the order in which they are given.

The subsequent line contains an integer q denoting the number of operations.

Each of the following q lines contains one operation in one of the following formats:

• C i w
• N u v
• SUM u v
• MAX u v
• MIN u v

outputFormat

For every operation of type SUM, MAX, or MIN, output the corresponding result on a separate line in the order the queries appear.

sample

5
0 1 1
1 2 2
1 3 3
3 4 4
7
SUM 0 2
MAX 2 4
MIN 0 4
N 1 3
SUM 0 4
C 3 -2
SUM 3 4

3
4
1
2
-2