P5980 [PA 2019] Herbata

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.

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$.

For each testdata, output one line. If a solution exists, output `TAK`; otherwise, output `NIE`.

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