Bajtazar 正在组织一场 Bajtograd 定向越野赛。比赛将在 Bajtograd 的街道上进行。该市的道路网络由 $n$ 个交叉路口和 $n - 1$ 条双向街道组成（从任何一个交叉路口都可以通过街道到达其他任何一个交叉路口）。

比赛将从起始交叉路口 $v_1$ 开始，参赛者必须跑到交叉路口 $v_2$（那里有定向任务中描述的第一个目标），然后必须跑到交叉路口 $v_3$（那里有第二个目标），最后回到起始交叉路口。

Bajtazar 正在思考如何选择交叉路口 $v_1, v_2$ 和 $v_3$，以使比赛尽可能有趣。其中一个标准是这些交叉路口之间的距离——既不能太小（以免参赛者太容易找到目标），也不能太大（以免参赛者因跑步而感到过于疲劳）。他准备了几个关于可能距离的方案，并针对每个方案思考是否存在一组交叉路口的选择能满足这些距离。请编写一个程序来帮助他。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$ ($3 \le n \le 300\,000, 1 \le q \le 200\,000$)，分别表示 Bajtograd 的交叉路口数量和方案数量。为方便起见，交叉路口编号为 $1$ 到 $n$。

接下来的 $n - 1$ 行描述了街道：每行包含两个整数 $a$ 和 $b$ ($1 \le a \neq b \le n$)，表示编号为 $a$ 和 $b$ 的交叉路口之间有一条双向街道。

接下来的 $q$ 行包含 Bajtazar 考虑的方案描述；每行包含三个整数 $d_{12}, d_{23}$ 和 $d_{31}$，取值范围在 $[0, n - 1]$，分别表示交叉路口 $v_1$ 与 $v_2$ 之间、交叉路口 $v_2$ 与 $v_3$ 之间以及交叉路口 $v_3$ 与 $v_1$ 之间的距离。

有时 Bajtazar 会考虑距离为零的情况（因此某些交叉路口在此时可能会重复）。

输出格式

输出应包含 $q$ 行，每行包含对输入中相应查询的回答。回答要么是一个单词 NIE（如果不存在所寻找的交叉路口三元组），要么是一个单词 TAK，后跟三个整数 $v_1, v_2$ 和 $v_3$。

如果存在多个解，你的程序可以输出其中任意一个。

子任务

如果你的程序在回答 TAK 时输出了错误的交叉路口编号，或者根本没有输出，它仍然可以获得该测试组 50% 的分数。

测试集分为以下子任务。每个子任务的测试由一个或多个单独的测试组组成。

样例

输入 1

6 4
1 2
2 3
2 5
2 4
5 6
3 2 3
1 2 3
1 1 1
3 0 3

输出 1

TAK 6 4 3
TAK 4 2 6
NIE
TAK 4 6 6