#3218. 「PA 2019」Herbata

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 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