Bajtolina 妈妈非常爱她的 Bajtoniątka（小 Bajton 们）。但她有点健忘，所以没有给他们起名字，而是为了方便，用从 1 到 $n$ 的自然数给他们编号。她每天为小 Bajton 们准备晚餐，并为每个小 Bajton 在他最喜欢的杯子里泡茶。杯子的容量各不相同：第 $i$ 个小 Bajton 的杯子容量为 $l_i$ 升，这正好是他晚餐时喜欢喝的量。然而，茶的体积并不是小 Bajton 们的唯一要求——茶的温度也必须合适。编号为 $i$ 的小 Bajton 希望他的茶温度正好是 $b_i$ 摄氏度。

不幸的是，一天晚上，健忘的 Bajtolina 把一切都搞混了，第 $i$ 个杯子里的茶温度正好是 $a_i$ 摄氏度。不过没关系——小 Bajton 们非常聪明，他们利用额外的杯子开始倒茶、混合和交换茶水。问题是：他们是否有可能通过这种方式达到目标，即得到 $n$ 杯茶，其中第 $i$ 杯的体积为 $l_i$ 升，温度为 $b_i$ 摄氏度？

形式上，小 Bajton 们可以执行有限次数的以下两个步骤： 分茶：拥有一个装有 $a$ 升温度为 $t$ 摄氏度的茶的杯子时，对于任何实数 $x$（$0 < x < a$），他们可以将它分成两个杯子，分别装有 $x$ 和 $a - x$ 升温度为 $t$ 摄氏度的茶。 混茶：拥有两个分别装有 $a$ 和 $b$ 升茶，温度分别为 $t_a$ 和 $t_b$ 摄氏度的杯子时，他们可以将它们混合，得到一个装有 $a+b$ 升茶的杯子，其温度为 $$\frac{a \cdot t_a + b \cdot t_b}{a + b}$$ 摄氏度，即两种温度的加权平均值。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 100\,000$)，表示测试用例的数量。 每个测试用例的描述以包含整数 $n$ ($1 \le n \le 100\,000$) 的行开始，表示小 Bajton 的数量。接下来是 $n$ 行描述小 Bajton 的信息；第 $i$ 行包含三个整数 $l_i, a_i, b_i$ ($1 \le l_i, a_i, b_i \le 1\,000\,000$)，分别表示第 $i$ 个小 Bajton 所需的茶体积（升）、初始温度和所需温度（摄氏度）。 所有测试用例中 $n$ 的总和不超过 $1\,000\,000$。

输出格式

输出 $t$ 行；第 $i$ 行应包含一个单词 TAK 或 NIE，取决于小 Bajton 们是否能在第 $i$ 个测试用例中达到目标。

样例

输入 1

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

输出 1

TAK
NIE
TAK
NIE
TAK

说明 1

将每个茶杯表示为一对数字。$(l, t)$ 表示一个装有 $l$ 升温度为 $t$ 摄氏度的茶的杯子。

在第一个测试用例中，小 Bajton 们最初有杯子 $(2, 1)$ 和 $(2, 5)$。通过分茶，他们可以从中得到一组杯子 $(\frac{1}{2}, 1), (1\frac{1}{2}, 1), (\frac{1}{2}, 5), (1\frac{1}{2}, 5)$。然后，混合杯子 $(\frac{1}{2}, 1)$ 和 $(1\frac{1}{2}, 5)$，得到 $\frac{1}{2} + 1\frac{1}{2} = 2$ 升温度为 $$\frac{\frac{1}{2} \cdot 1 + 1\frac{1}{2} \cdot 5}{\frac{1}{2} + 1\frac{1}{2}} = 4$$ 的茶，即杯子 $(2, 4)$。同样，混合 $(1\frac{1}{2}, 1)$ 和 $(\frac{1}{2}, 5)$，得到 $(2, 2)$。最终，小 Bajton 们将拥有两个体积和温度都符合要求的杯子。

在第二个测试用例中，小 Bajton 们的两杯茶都太热了。不幸的是，分茶和混茶都无济于事。

在第三个测试用例中，小 Bajton 们只需要交换杯子即可。

子任务

在某些测试组中（至少一组），所有 $l_i$ 的值都正好为 1。换句话说，所有杯子的容量正好为 1 升。