You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

题目描述

爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有 $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 结束。

输出格式

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

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

9
16

提示

对于全部数据，$1\le N\le 10^5$，操作和询问数目不超过 $10^5$。

保证在任意时刻，所有树枝上毛毛果的个数都不会超过 $10^9$ 个。