题目描述

Ray 乐忠于旅游，这次他来到了 T 城。T 城是一个水上城市，一共有 $n$ 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说，T 城中只有 $n − 1$ 座桥。

Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度 $w$，也就是说，Ray 经过这座桥会增加 $w$ 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。

现在，Ray 想让你帮他计算从 $u$ 景点到 $v$ 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。

输入格式

输入的第一行包含一个整数 $n$，表示 T 城中的景点个数。景点编号为 $0\sim n − 1$。

接下来 $n − 1$ 行，每行三个整数 $u,v,w$，表示有一条 $u$ 到 $v$，使 Ray 愉悦度增加 $w$ 的桥。桥的编号为 $1\sim n − 1$。

输入的第 $n + 1$ 行包含一个整数 $m$，表示 Ray 的操作数目。

接下来有 $m$ 行，每行描述了一个操作，操作有如下五种形式：

• C i w，表示 Ray 对于经过第 $i$ 座桥的愉悦度变成了 $w$。
• N u v，表示 Ray 对于经过景点 $u$ 到 $v$ 的路径上的每一座桥的愉悦度都变成原来的相反数。
• SUM u v，表示询问从景点 $u$ 到 $v$ 所获得的总愉悦度。
• MAX u v，表示询问从景点 $u$ 到 $v$ 的路径上的所有桥中某一座桥所提供的最大愉悦度。
• MIN u v，表示询问从景点 $u$ 到 $v$ 的路径上的所有桥中某一座桥所提供的最小愉悦度。

输出格式

对于每一个询问（操作SUM、MAX 和 MIN），输出答案。

样例输入

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

数据规模与约定

一共有 10 个数据，对于第 $i(1\leq i\leq 10)$，$n=m=i\times 2\times 10^3$。

对于输入数据中的 $w$，保证 $|w|\leq 10^3$。