Tea

Bytemommy whole-heartedly loves her Bytekids. However she is kinda forgetful, so instead of giving them proper names, she numbered them with consecutive integers from $1$ to $n$. Every day she prepares a tea for each of her Bytekids in their favourite cups. One peculiar property of all tea cups in their home is that they have infinite capacity, even though they take finite space only. However, this is for our simplicity only. Bytekid number $i$ prefers to drink exactly $l\_i$ bitres of tea every day. However, the amount of tea is not their only requirement. Its temperature has to be properly adjusted as well. Bytekid number $i$ would like its tea to have exactly $b\_i$ Bytesius degrees.

Unfortunately, one day scatterbrained Bytemommy messed up the tea temperatures and the temperature of the tea in the $i$-th cup was exactly $a\_i$ Bytesius degrees, instead of $b\_i$ (however the $i$-th kid still got $l\_i$ bitres in its cup). Nothing is lost yet. Bytekids are very clever and, using some auxiliary cups, started to mix up their teas trying to get cups with appropriate amounts and temperatures of teas. You need to determine whether it is possible for Bytekids to reach their goal, that is to get $n$ teas so that the $i$-th tea has exactly $l\_i$ bitres and $b\_i$ Bytesius degrees.

Formally, Bytekids are allowed to perform the following steps arbitrarily many times:

• Partitioning the tea. Given a cup with $a$ bitres of tea with temperature $t$, create two cups of tea with $x$ and $a-x$ bitres of tea with temperature $t$ for some arbitrary real value of $x$ such that $0<x<a$ (the initial cup of tea will no longer exist, obviously).
• Mixing the tea. Given two cups of tea with $a$ and $b$ bitres of tea with temperatures $t\_a$ and $t\_b$, respectively, create one cup of tea with $a+b$ bitres of tea with temperature $\frac{a \cdot t\_a + b \cdot t\_b}{a + b},$ that is, the weighted mean of the initial temperatures (again, the initial two cups of tea will no longer exist).

The first line of input contains one integer $t$ ($1 \le t \le 100\,000$) denoting the number of testcases.

The description of each testcase starts with a line containing one integer $n$ ($1 \le n \le 100\,000$) denoting the number of Bytekids. The following $n$ lines describe the Bytekids: the $i$-th of them contains three integers $l\_i$, $a\_i$ and $b\_i$ ($1 \le l\_i, a\_i, b\_i \le 1\,000\,000$) denoting the amount of tea in the $i$-th cup in bitres (both the initial and the required final one) and the initial and required temperature of that tea, respectively.

The sum of the values of $n$ over all testcases will not exceed $1\,000\,000$.

You need to print $t$ lines. The $i$-th of them should contain the word TAK if it is possible for Bytekids to reach their goal in the $i$-th testcase, or NIE otherwise.

Denote cups of tea as a pair of numbers. The pair $(l, t)$ denotes a cup with $l$ bitres of tea with temperature $t$ Bytesius degrees.

In the first testcase Bytekids have cups $(2, 1)$ and $(2, 5)$. Using the operation of partitioning the tea they can get cups $(\frac12, 1)$, $(\frac32, 1)$, $(\frac12, 5)$ and $(\frac32, 5)$.

Then, by mixing cups $(\frac12, 1)$ and $(\frac32, 5)$, they get $\tfrac12 + \tfrac32 = 2$ bitres with temperature

$\frac{\frac12 \cdot 1 + \frac32 \cdot 5}{\frac12 + \frac32} = 4,$

that is, the cup $(2,4)$. Similarly, by mixing the cup $(\frac32, 1)$ with $(\frac12, 5)$, they get $(2, 2)$. In the end, Bytekids will have two cups with appropriate amounts and temperatures of tea.

In the second testcase both teas are too hot. We can't do much here.

However, in the third testcase it is sufficient for Bytekids to swap their cups.