Herbata

题目描述

题目译自 PA 2019 Runda 2 Herbata

你有无穷多个容量无限的杯子以及 $n$ 杯水，第 $i$ 杯水的体积为 $l_i$，温度为 $a_i$。

你可以做无限次操作，每次操作是下面两种操作之一：

1. 选择一杯水，假设它的体积为 $V$，温度为 $T$，那么你可以将其倒入若干个空杯中，使得每一杯的水的温度都为 $T$，且体积之和等于 $V$，注意体积可以是任意非负实数。
2. 选择两杯水，假设一杯的体积为 $V_a$，温度为 $T_a$，另一杯的体积为 $V_b$，温度为 $T_b$，那么你可以将这两杯水混合为一杯体积为 $V_a + V_b$，温度为 $\frac{V_a T_a + V_b T_b}{V_a + V_b}$的水。

你的目标进行若干次操作，使得操作完毕后，对于所有的 $i$（$1 \le i \le n$）都有第 $i$ 杯水的体积等于 $l_i$，温度等于 $b_i$。请写一个程序判断是否有解。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个正整数 $n$。接下来 $n$ 行，每行三个正整数 $l_i, a_i, b_i$。

输出格式

对于每组数据输出一行，如果有解，输出 TAK，否则输出 NIE。

样例

输入

5
2
2 1 4
2 5 2
2
1 4 3
1 5 4
2
1 5 7
1 7 5
2
1 4 1
1 2 5
3
2 6 4
1 2 3
3 4 5

输出

TAK
NIE
TAK
NIE
TAK

数据范围与提示

• $1 \le T \le 10^5$
• $1 \le n \le 10^5$
• $1 \le l_i, a_i, b_i \le 10^6$
• 输入数据保证所有的 $n$ 加起来不超过 $10^6$