#5546. [PA2019]Herbata

内存限制:256 MiB 时间限制:20 Sec

题目描述

你有无穷多个容量无限的杯子以及n杯水,第i杯水的体积为l[i],温度为a[i]。
你可以做无限次操作,每次操作是下面两种操作之一:
1. 选择一杯水,假设它的体积为V,温度为T,那么你可以将其倒入若干个空杯中,使得每一杯的水的温度都为T,且体积之和等于V,注意体积可以是任意非负实数。
2. 选择两杯水,假设一杯的体积为V_a,温度为T_a,另一杯的体积为V_b,温度为T_b,那么你可以将这两杯水混合为一杯体积为V_a+V_b,温度为(V_a*T_a+V_b*T_b)/(V_a+V_b)的水。
你的目标进行若干次操作,使得操作完毕后,对于所有的i(1<=i<=n)都有第i杯水的体积等于l[i],温度等于b[i]。请写一个程序判断是否有解。

输入格式

第一行包含一个正整数T(1<=T<=100000),表示测试数据的组数。
每组测试数据第一行包含一个正整数n(1<=n<=100000)。
接下来n行,每行三个正整数l[i],a[i],b[i](1<=l[i],a[i],b[i]<=1000000)。
输入数据保证所有的n加起来不超过1000000。

输出格式

对于每组数据输出一行,如果有解,输出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

数据范围与提示