409026 - 毛毛果

一棵有 N 个节点的树,共 N - 1 条树枝,每条树枝上有若干毛毛果。需要支持以下操作: 1.Change k w:将第 k 条树枝上的毛毛果个数改为 w。 2.Cover u v w:将结点 u 到结点 v 路径上所有树枝的毛毛果个数都改为 w。 3.Add u v w:将结点 u 到结点 v 路径上所有树枝的毛毛果个数都增加 w。 4.Max u v:询问结点 u 到结点 v 路径上树枝毛毛果个数的最大值。

Input

第一行一个正整数 N。 接下来 N - 1 行,每行三个正整数 Ui、Vi、Wi,描述第 i 条树枝连接结点 Ui 和 Vi,上面有 Wi 个毛毛果。 接下来若干行,每行为上述四种操作之一,以 Stop 结束。

Output

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

Examples

Input

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

Output

9
16

Hint

1 ≤ N ≤ 100000,操作和询问总数不超过 100000。任意时刻所有树枝上毛毛果个数不超过 10^9。

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题