The first snow of the season has fallen in Bajtogóra tonight. As the mayor of this city, you have decided to celebrate this and, while clearing the roads, build a giant snowman. The city has $n$ intersections, numbered from 1 to $n$, connected by $n-1$ bidirectional streets (dead-end streets also end at intersections). It is possible to reach any intersection from any other intersection using these streets. For each street, it is known which two intersections it connects and what its length is. The snow fell evenly everywhere, meaning that $w$ units of snow fell on a road of length $w$.

The snowman will consist of three snowballs, each created by rolling a ball through all the snow on a certain path. Such a path can start at an intersection or at any point on any street. It then passes through a sequence of distinct streets and intersections, until it finally ends at any point on a street or at an intersection. The finished ball will be transported by helicopter to the snowman's construction site.

No two paths can pass through the same point, as this would cause the balls to get dirty with mud. More precisely, no point on the map of Bajtogóra, especially an intersection, can be an internal point of two different paths. We assume that we do not collect snow at the point where we start or finish rolling a ball, so more than one path can start or end at a single point (and a path can also start or end at an internal point of another path).

You have not yet decided how large the individual snowballs will be, so it is unknown how much snow will be needed for them. You are considering $q$ potential projects; each of them is described by three integers $a_i \le b_i \le c_i$, representing the sizes of the individual snowballs (from the top to the bottom of the snowman).

For each project, determine if it is possible to build a snowman in the above manner.

Input

The first line of input contains two integers $n$ and $q$ ($2 \le n \le 200\,000$, $1 \le q \le 200\,000$), representing the number of intersections in Bajtogóra and the number of snowman projects, respectively.

The next $n-1$ lines contain descriptions of the streets; each consists of three integers $u_i$, $v_i$, and $w_i$ ($1 \le u_i, v_i \le n$; $1 \le w_i \le 10^9$), describing the street connecting intersections $u_i$ and $v_i$, on which there are $w_i$ units of snow.

Then, the next $q$ lines contain the snowman projects. Each consists of three integers $a_i$, $b_i$, and $c_i$ ($1 \le a_i \le b_i \le c_i \le 10^{15}$), describing the sizes of the individual balls in the $i$-th snowman project.

Output

Output $q$ lines; the $i$-th line should contain the word TAK if it is possible to build the snowman from the $i$-th project, or the word NIE otherwise.

Examples

Input 1

9 11
1 2 25
2 3 2
2 4 5
1 5 5
1 6 6
1 7 1
7 8 2
7 9 2
57 57 57
12 12 12
6 8 30
1 8 31
7 7 25
10 15 15
5 11 27
5 7 31
4 5 36
12 12 13
7 7 26

Output 1

NIE
TAK
TAK
NIE
TAK
TAK
TAK
TAK
TAK
NIE
NIE

Subtasks

Test groups are sorted by an additional constraint on the value of $n$.

• Group 1: The sum of values $w_i$ does not exceed 60.
• Group 2: $n \le 1000$, $q \le 1000$.
• Group 3: $q \le 200$.
• Group 4: $n \le 100\,000$.
• Group 5: No additional constraints.

In groups 1, 3, and 5, there is an additional condition $q \le 200$.