The Funny Informatics Contest

Olgierd, the hero of this problem, is a high-school student just like you. He practices on various online judges, hoping to reach the finals of the Polish Olympiad in Informatics.

His next step is the Funny Informatics Contest (ŚKI). The contest is made up of many rounds whose time spans may overlap one another arbitrarily. Each round comes with exactly one problem.

Olgierd does not know the problems yet, but he has already decided how much time to spend on each round. Once he starts a problem, he works on it without any break for exactly the time he planned (caffeine helps). The rules are:

• At any single moment he can work on only one problem.
• He cannot start a round's problem before that round begins (he does not know the problems), and he will not work on it after that round ends.
• Each problem is solved in one continuous stretch of the planned length (it cannot be split).

Because the ŚKI problems are very hard, the time Olgierd plans for each round is at least half of that round's total length.

Determine whether he can spend exactly the planned amount of time on every round.

Formally, there are $n$ rounds. Round $i$ takes place inside the time interval $[a_i, b_i]$. Olgierd wants to spend a continuous block of length $c_i$ on it, and this block must lie entirely within $[a_i, b_i]$. Blocks of different rounds may not overlap in time (touching at an endpoint is allowed). For every round it is guaranteed that $\frac{b_i - a_i}{2} \le c_i$. Decide whether such a non-overlapping assignment exists.

The first line contains the number of data sets (test cases) $z$.

The first line of each data set contains the number of rounds $n$ ($1 \le n \le 2 \cdot 10^5$). Each of the next $n$ lines describes one round with three integers $a_i$, $b_i$, $c_i$ ($0 \le a_i < b_i \le 10^9$, $\frac{b_i - a_i}{2} \le c_i \le b_i - a_i$): round $i$ starts at time $a_i$, ends at time $b_i$, and Olgierd wants to spend $c_i$ units of time on it. The sum of $n$ over all data sets does not exceed $10^6$.

For each data set output a single line: TAK if Olgierd can carry out his plan, or NIE if it is impossible. (TAK means "yes" and NIE means "no".)