409016 - 树的查询

现在你有一棵树,共有 n(n ≤ 100000)个结点,由 1 至 n 依次编号。有 n – 1 条边,每条边有一个权值,由 1 至 n – 1 依次编号。现在你要完成一些指令,这些指令包括: CHANGE i v,表示将第 i 条边的权值改为 v; QUERY a b,表示将结点 a 到结点 b 路径上的最大权值输出。

Input

第一个为一个整数 m,表示有 m 组数据。 第二行为一个整数 n,表示结点个数。 接下来 n – 1 行分别有 3 个整数,分别表示该条边的结点编号和权值。 然后是若干条指令要求(不超过 3 × 10^5),指令格式见上文说明,最后以 “DONE” 结束。

Output

对于每个查询指令,输出答案一行。

Examples

Input

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Output

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