有 $N$ 个顶点构成的树（无向无环连通图）。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。
请编写一个程序执行下面两种查询：
1 u v：输出从 $u$ 到 $v$ 路径的代价。2 u v k：输出从 $u$ 到 $v$ 路径上第 $k$ 个顶点。$k$ 不超过路径上包含的顶点个数。
输入格式
第一行给出 $N$ ($2 \le N \le 100{,}000$)。
接下来 $N-1$ 行，每行给出第 $i$ 条边连接的两个顶点编号 $u$ 和 $v$ 以及边的代价 $w$。
下一行给出查询个数 $M$ ($1 \le M \le 100{,}000$)。
接下来 $M$ 行，每行给出一个查询。
边的代价是始终不超过 $1{,}000{,}000$ 的自然数。
输出格式
按顺序每行输出一个查询的结果。
样例
输入 1
6 1 2 1 2 4 1 2 5 2 1 3 1 3 6 2 2 1 4 6 2 4 6 4
输出 1
5 3