Background

Warning: abusing this problem’s judging system will result in a ban after just once.

“zbugujemy” (English “bug”): to cause a malfunction / to debug.

Problem Description

Tonight, the first snow of this year fell on Bajtogóra. As the mayor of the city, you decide to take the chance during snow removal to build a huge snowman to celebrate this moment. The city has $n$ intersections, numbered from 1 to $n$, connected by $n-1$ bidirectional streets (there are intersections even at the ends of dead ends). From any intersection, you can reach any other intersection by following the streets. For each street, you are given the two intersections it connects and its length. Snow falls evenly everywhere, so a road of length $w$ has $w$ units of snow on it.

The snowman consists of three snowballs, and each snowball is made by rolling snow along some simple path. A path may start at an intersection or at any point on a street, pass through several distinct streets and intersections, and finally end at any point on a street or at an intersection. The finished snowballs will be transported by helicopter to the construction site.

No two paths may pass through the same point; otherwise, the snowballs would get covered in mud. More precisely, any point on the map of Bajtogóra (in particular, any intersection) cannot be an internal point of two different paths. We assume that no snow is collected at the point where rolling starts or ends, so the same point may be the start or end of multiple paths (also, a path may start or end at an internal point of another path).

You have not yet decided the sizes of the snowman’s parts, so you do not know how much snow each snowball needs. You are considering $q$ possible plans; each plan is described by three integers $a_i \le b_i \le c_i$, representing the sizes of the snowballs (from top to bottom).

For each plan, determine whether it is possible to build the snowman in the way described above.

Input Format

The first line 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 plans.

The next $n-1$ lines each contain 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 a street connecting intersections $u_i$ and $v_i$, and there are $w_i$ units of snow on this street.

The next $q$ lines each describe a snowman plan, containing three integers $a_i, b_i, c_i$ ($1 \le a_i \le b_i \le c_i \le 10^{15}$), describing the sizes of the snowballs in the $i$-th plan.

Output Format

Output $q$ lines in total. If the $i$-th plan can be built, output TAK on the $i$-th line; otherwise output NIE.

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

NIE
TAK
TAK
NIE
TAK
TAK
TAK
TAK
TAK
NIE
NIE

Hint

Explanation of the Samples

\begin{aligned} \end{aligned}

• The first plan (snowball sizes $57, 57, 57$) is impossible. There is not enough snow in the city to build such a huge snowman.

• To build a snowman $12, 12, 12$, you can use the following paths:

  • $6-1-2$ (only part of the last street is used), collecting $6 + 6 = 12$ units of snow.
  • $4-2-1$ (only part of the last street is used), collecting $5 + 7 = 12$ units of snow.
  • The remaining part of street $1-2$ has $25 - 6 - 7 = 12$ units of snow left, enough to build the third snowball.

• To build a snowman $6, 8, 30$, you can use the following paths:

  • $1-6$, collecting $6$ units of snow.
  • $5-1-7-8$, collecting $5 + 1 + 2 = 8$ units of snow.
  • $1-2-4$, collecting $25 + 5 = 30$ units of snow.

  Note that intersection $1$ is an internal point of only one path, so no snowball will get covered in mud.

• To build a snowman $1, 8, 31$, you cannot use the following paths:

  • $2-3$,
  • $5-1-6$,
  • $7-1-2-4$.

  Although there is enough snow, two paths use the snow at intersection $1$, which would cause one of the snowballs to get covered in mud.

• To build a snowman $7, 7, 25$, you can use the following paths:

  • $3-2-4$, collecting $2 + 5 = 7$ units of snow.
  • $6-1-7$, collecting $6 + 1 = 7$ units of snow.
  • $1-2$, collecting $25$ units of snow.

Subtasks

The test groups are ordered by the value of $n$ under additional constraints. In group 1, the sum of $w_i$ does not exceed $60$. In groups 1, 3, and 5, there is an additional condition $q \le 200$.

Input Format

Output Format

Hint

Translated by ChatGPT 5