月下“毛景树”

题目背景

毛毛虫经过及时的变形,最终逃过的一劫,离开了菜妈的菜园。 毛毛虫经过千山万水,历尽千辛万苦,最后来到了小小的绍兴一中的校园里。

题目描述

爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面,发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有 $N$ 个节点和 $N-1$ 条树枝,但节点上是没有毛毛果的,毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力,他能改变树枝上毛毛果的个数: - `Change k w`:将第k条树枝上毛毛果的个数改变为 $w$ 个。 - `Cover u v w`:将节点 $u$ 与节点 $v$ 之间的树枝上毛毛果的个数都改变为 $w$ 个。 - `Add u v w`:将节点 $u$ 与节点 $v$ 之间的树枝上毛毛果的个数都增加 $w$ 个。 由于毛毛虫很贪,于是他会有如下询问: - `Max u v`:询问节点 $u$ 与节点 $v$ 之间树枝上毛毛果个数最多有多少个。

输入输出格式

输入格式


第一行一个正整数 $N$。 接下来 $N-1$ 行,每行三个正整数 $U_i,V_i$ 和 $W_i$,第 $i+1$ 行描述第 $i$ 条树枝。表示第 $i$ 条树枝连接节点 $U_i$ 和节点 $V_i$,树枝上有 $W_i$ 个毛毛果。 接下来是操作和询问,以 `Stop` 结束。

输出格式


对于毛毛虫的每个询问操作,输出一个答案。

输入输出样例

输入样例 #1

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

输出样例 #1

9
16

说明

对于全部数据,$1\le N\le 10^5$,操作和询问数目不超过 $10^5$。 保证在任意时刻,所有树枝上毛毛果的个数都不会超过 $10^9$ 个。