题目描述

有 $N$ 个点，编号为 $1 \sim N$，有 $N-1$ 条边，每条边都有长度。

有若干个操作，操作分为两种

DIST $u$ $v$：表示询问 $u$ 到 $v$ 的距离。

KTH $u$ $v$ $k$：表示询问从 $u$ 到 $v$ 路径上第 $k$ 个点的编号（保证路径上至少 $k$ 个点）。

输入格式

第一行输入一个整数 $N$，表示有 $N$ 个点（$1 \le N \le 10^6$）

下来 $N-1$ 行每行输入三个整数 $x，y，c$，表示点 $x$ 到点 $y$ 有一条长度为 $c$ 的边。

下来若干个操作。读入“DONE”时停止。

操作详情见题目描述。

输出格式

对于每次操作输出相应答案即可。

6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
DIST 4 6
KTH 4 6 4
DONE

5
3