Bajtogóra 昨晚下了第一场雪。作为市长，你决定庆祝这一时刻，并借着清理道路的机会堆一个大雪人。城里有 $n$ 个路口，编号从 $1$ 到 $n$，由 $n-1$ 条双向街道连接（死胡同的尽头也有路口）。从任何一个路口都可以通过街道到达其他任何路口。对于每条街道，已知它连接哪两个路口及其长度。雪均匀地落在各处，即长度为 $w$ 的道路上落下了 $w$ 单位的雪。

雪人由三个雪球组成，每个雪球都是通过在某条路径上收集所有积雪而滚成的。这样的路径可以从一个路口开始，也可以从任意街道上的任意一点开始。随后，它经过一系列不同的街道和路口，最后在街道上的任意一点或路口结束。滚好的雪球将由直升机运送到雪人建造地点。

任何两条路径都不能经过同一个点，因为这会导致雪球沾上泥土。更准确地说，Bajtogóra 地图上的任何点，特别是路口，都不能是两条不同路径的内部点。我们假设在开始或结束滚雪球的点上不收集积雪，因此一个点可以作为多条路径的起点或终点（路径也可以在另一条路径的内部点开始或结束）。

你还没有决定雪人的各个雪球会有多大，因此不知道需要多少雪。你正在考虑 $q$ 个潜在的方案；每个方案由三个整数 $a_i \le b_i \le c_i$ 描述，分别表示雪球的大小（从雪人顶部到底部）。

对于每个方案，请确定是否可以按照上述方式建造雪人。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 200\,000, 1 \le q \le 200\,000$)，分别表示 Bajtogóra 的路口数量和雪人方案数量。

接下来的 $n-1$ 行包含街道描述；每行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n; 1 \le w_i \le 10^9$)，描述连接路口 $u_i$ 和 $v_i$ 的街道，其上有 $w_i$ 单位的雪。

接下来的 $q$ 行包含雪人方案。每行包含三个整数 $a_i, b_i$ 和 $c_i$ ($1 \le a_i \le b_i \le c_i \le 10^{15}$)，描述第 $i$ 个方案中各个雪球的大小。

输出格式

输出 $q$ 行；如果可以根据第 $i$ 个方案建造雪人，则第 $i$ 行应包含一个单词 TAK，否则输出 NIE。

样例

输入格式 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

输出格式 1

NIE
TAK
TAK
NIE
TAK
NIE
TAK
TAK
TAK
NIE
NIE

说明

Bajtogóra 的城市地图

• 第一个方案（雪球大小为 57, 57, 57）无法建造。城里的雪不足以堆出这么大的雪人。
• 建造 12, 12, 12 的雪人可以使用以下路径：
  • 6—1—2（部分使用最后一条街道），收集 6 + 6 = 12 单位的雪。
  • 4—2—1（部分使用最后一条街道），收集 5 + 7 = 12 单位的雪。
  • 在街道 1—2 的剩余部分还剩下 25 - 6 - 7 = 12 单位的雪，足以建造第三个雪球。
• 建造 6, 8, 30 的雪人可以使用以下路径：
  • 1—6，收集 6 单位的雪。
  • 5—1—7—8，收集 5 + 1 + 2 = 8 单位的雪。
  • 1—2—4，收集 25 + 5 = 30 单位的雪。 注意，路口 1 仅位于一条路径的内部，因此没有任何雪球会沾上泥土。
• 建造 1, 8, 31 的雪人无法使用以下路径：
  • 2—3,
  • 5—1—6,
  • 7—1—2—4. 尽管雪的总量足够，但两条路径会使用路口 1 的雪，这会导致其中一个雪球沾上泥土。
• 建造 7, 7, 25 的雪人可以使用以下路径：
  • 3—2—4，收集 2 + 5 = 7 单位的雪。
  • 6—1—7，收集 6 + 1 = 7 单位的雪。
  • 1—2，收集 25 单位的雪。

子任务

测试组按 $n$ 的附加限制排序。在第 1 组中，$w_i$ 的总和不超过 60。在第 1、2、3、4 和 5 组中，满足附加条件 $q \le 200$。