题目描述

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

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

1. 选择一杯水，假设它的体积为 $V$，温度为 $T$，那么你可以将其倒入若干个空杯中，使得每一杯的水的温度都为 $T$，且体积之和等于 $V$，注意体积可以是任意非负实数。

2. 选择两杯水，假设一杯的体积为 $V_a$，温度为 $T_a$，另一杯的体积为 $V_b$，温度为 $T_b$，那么你可以将这两杯水混合为一杯体积为 $V_a+V_b$，温度为 $\dfrac{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

提示

对于 $100\%$ 的数据，$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$。