Description

You have infinitely many cups with unlimited capacity and $n$ cups of water. The $i$-th cup has volume $l_i$ and temperature $a_i$.

You can perform infinitely many operations. Each operation is one of the following:

1. Choose one cup of water. Suppose its volume is $V$ and its temperature is $T$. You may pour it into several empty cups so that the temperature of water in each cup is still $T$, and the sum of their volumes equals $V$. Note that the volumes can be any non-negative real numbers.

2. Choose two cups of water. Suppose one has volume $V_a$ and temperature $T_a$, and the other has volume $V_b$ and temperature $T_b$. You may mix them into one cup of water with volume $V_a+V_b$ and temperature $\dfrac{V_a\times T_a+V_b\times T_b}{V_a+V_b}$.

Your goal is to perform some operations so that after all operations, for every $i(1\le i\le n)$, the $i$-th cup has volume $l_i$ and temperature $b_i$. Write a program to determine whether a solution exists.

Input Format

The first line contains a positive integer $T$, denoting the number of testdata.

For each testdata, the first line contains a positive integer $n$.

The next $n$ lines each contain three positive integers $l_i,a_i,b_i$.

Output Format

For each testdata, output one line. If a solution exists, output TAK; otherwise, output 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

Hint

For $100\%$ of the testdata, $1\le T\le 10^5$, $1\le n\le 10^5$, $1\le l_i,a_i,b_i\le 10^6$. The input guarantees that the sum of all $n$ does not exceed $10^6$ across all testdata.

Translated by ChatGPT 5