Description

村里有n栋房屋，有一些双向道路将它们连接起来。每天人们总是喜欢这样问：“如果我想从房子A到房子B多远？”，一开始，道路的建造方式是每两栋房屋之间都有一条唯一的简单路径（“简单”意味着你不能两次访问某个地方）。随着时间推移，会有新的房屋加入该交通(即新的房屋(编号>n)会和当前的已经在交通网络中的房屋连接)，房屋的编号从1开始。

Format

Input

第一行中都有两个数字n（2 <= n <= 40000）和m（1 <= m <= 200），房屋数和操作数。接下来的n-1行每行由三个数字i，j，k隔开，并且在一个空格中隔开，这意味着存在一条连接房屋i和房屋j的道路，长度为k（0 <k <= 40000）。从1到n标记。接下来的m行表示m个操作，操作有两种，分别为ADD和 Q： ①ADD x y z表示x和y之间加入一条边，权值为z，保证x和y中的某个为新加入的村庄，数据保证最终的交通下房屋总数不超过40000。 ②Q x y :表示查询x和y的距离，如果x和y之间不联通，输出too far。

Output

对于每个Q，输出x和y之间的距离。

Sample 1

Input

3 4
1 2 10
3 1 15
ADD 5 1 10
Q 4 5
ADD 4 3 56
Q 4 5

Output

too far
81

Limitation

1s, 1024KiB for each test case.