Description

给定一棵 $n$ 个节点的树，边带权，编号 $0 \sim n-1$，需要支持五种操作：

• C i w 将输入的第 $i$ 条边权值改为 $w$；
• N u v 将 $u,v$ 节点之间的边权都变为相反数；
• SUM u v 询问 $u,v$ 节点之间边权和；
• MAX u v 询问 $u,v$ 节点之间边权最大值；
• MIN u v 询问 $u,v$ 节点之间边权最小值。

保证任意时刻所有边的权值都在 $[-1000,1000]$ 内。

Input Format

第一行一个正整数 $n$，表示节点个数。
接下来 $n-1$ 行，每行三个整数 $u,v,w$，表示 $u,v$ 之间有一条权值为 $w$ 的边，描述这棵树。
然后一行一个正整数 $m$，表示操作数。
接下来 $m$ 行，每行表示一个操作。

Output Format

对于每一个询问操作，输出一行一个整数表示答案。

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

【数据范围】

对于 $100\%$ 的数据，$1\le n,m \le 2\times 10^5$。

2020.02.04 修正了一点数据的错误
2020.03.14 加入了一组 hack 数据
2020.11.26 加入了一组 hack 数据 By @_Leaving