Bajtazar is organizing the Bajtograd Orienteering Race. The race will take place on the streets of Bajtograd. The city's road network consists of $n$ intersections connected by $n - 1$ bidirectional streets (it is possible to travel between any two intersections).

The race will start at an initial intersection $v_1$, after which the participants must run to intersection $v_2$, where the first object described in the orienteering task is located, then they must run to intersection $v_3$, where the second object is located, and finally return to the starting intersection.

Bajtazar is wondering how to choose the intersections $v_1, v_2,$ and $v_3$ to make the race as interesting as possible. One of the criteria is the distance between these intersections – it cannot be too small (so that it is not too easy for the participants to find the object) nor too large (so that they do not get too tired of running). He has prepared several variants of possible distances and, for each variant, is wondering if there exists a choice of intersections that realizes these distances. Write a program that will help him with this.

Input

The first line of the input contains two integers $n$ and $q$ ($3 \le n \le 300\,000$, $1 \le q \le 200\,000$) denoting the number of intersections in Bajtograd and the number of variants. For simplicity, the intersections are numbered from $1$ to $n$.

The next $n - 1$ lines contain the description of the streets: each of them contains two integers $a$ and $b$ ($1 \le a \neq b \le n$) denoting a bidirectional street between intersections numbered $a$ and $b$.

The next $q$ lines contain the descriptions of the variants considered by Bajtazar; each of them contains three integers $d_{12}, d_{23},$ and $d_{31}$ from the interval $[0, n - 1]$, which denote the distances between intersections $v_1$ and $v_2$, between intersections $v_2$ and $v_3$, and between intersections $v_3$ and $v_1$, respectively.

Sometimes Bajtazar considers a situation where the distance is equal to zero (so some intersections may repeat in that case).

Output

For each query, output a single line containing the answer. The answer is either the word NIE if the sought triple of intersections does not exist, or the word TAK followed by three integers $v_1, v_2,$ and $v_3$.

If there is more than one solution, your program may output any of them.

Examples

Input 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

Output 1

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

Subtasks

If your program outputs incorrect intersection numbers for a TAK answer or does not output them at all, it will still receive 50% of the points for that test group.

The test set is divided into the following subtasks: