차

Bytemommy는 자기 Bytekids를 진심으로 아낀다. 그런데 좀 잘 잊어버리는 편이라, 아이들에게 제대로 된 이름을 붙여 주는 대신 $1$부터 $n$까지의 연속된 정수로 번호를 매겼다. 매일 그녀는 Bytekids 각자에게 그 아이가 좋아하는 컵에 담아 차를 준비한다. 이 집의 모든 찻잔은 한 가지 특이한 성질을 지니는데, 유한한 공간만 차지하는데도 용량이 무한하다. 다만 이건 우리의 편의를 위한 것일 뿐이다. $i$번 Bytekid는 매일 정확히 $l\_i$ bitre의 차를 마시는 것을 좋아한다. 그런데 차의 양만이 아이들의 요구 사항은 아니다. 온도도 적절히 맞춰져야 한다. $i$번 Bytekid는 자기 차의 온도가 정확히 $b\_i$ Bytesius 도이기를 바란다.

안타깝게도 어느 날 덜렁대는 Bytemommy가 차의 온도를 뒤죽박죽으로 만들어, $i$번 컵에 담긴 차의 온도가 $b\_i$가 아니라 정확히 $a\_i$ Bytesius 도가 되었다. 물론 $i$번 아이는 여전히 자기 컵에 $l\_i$ bitre를 받았다. 아직 다 잃은 것은 아니다. Bytekids는 매우 영리해서, 몇 개의 보조 컵을 이용해 자기들의 차를 섞기 시작했고, 알맞은 양과 온도의 차가 담긴 컵을 얻으려 한다. Bytekids가 목표를 달성할 수 있는지, 즉 $i$번 차가 정확히 $l\_i$ bitre이고 $b\_i$ Bytesius 도가 되도록 $n$개의 차를 얻을 수 있는지 판별해야 한다.

형식적으로, Bytekids는 다음 단계를 임의의 횟수만큼 수행할 수 있다.

• 차 나누기. $a$ bitre의 차가 담긴 온도 $t$인 컵이 주어졌을 때, $0<x<a$인 임의의 실수 $x$에 대해 온도 $t$인 $x$ bitre의 차가 담긴 컵과 $a-x$ bitre의 차가 담긴 컵 두 개를 만든다. 처음 컵의 차는 당연히 더 이상 존재하지 않는다.
• 차 섞기. 각각 온도 $t\_a$, $t\_b$인 $a$ bitre, $b$ bitre의 차가 담긴 컵 두 개가 주어졌을 때, 온도가 $\frac{a \cdot t\_a + b \cdot t\_b}{a + b}$인 $a+b$ bitre의 차가 담긴 컵 하나를 만든다. 즉 처음 두 온도의 가중 평균이다. 여기서도 처음 두 컵의 차는 더 이상 존재하지 않는다.

첫 줄에 테스트케이스의 수를 나타내는 정수 $t$가 주어진다. ($1 \le t \le 100\,000$)

각 테스트케이스의 설명은 Bytekids의 수를 나타내는 정수 $n$이 있는 줄로 시작한다. ($1 \le n \le 100\,000$) 다음 $n$개의 줄이 Bytekids를 설명한다. 그중 $i$번째 줄에는 세 정수 $l\_i$, $a\_i$, $b\_i$가 주어지며, 각각 $i$번 컵에 담긴 차의 양(처음과 요구되는 최종 양 모두)을 bitre로, 그리고 그 차의 처음 온도와 요구 온도를 나타낸다. ($1 \le l\_i, a\_i, b\_i \le 1\,000\,000$)

모든 테스트케이스에 걸친 $n$ 값의 합은 $1\,000\,000$을 넘지 않는다.

$t$개의 줄을 출력해야 하며, 그중 $i$번째 줄에는 $i$번 테스트케이스에서 Bytekids가 목표를 달성할 수 있으면 TAK, 아니면 NIE를 출력한다.

차가 담긴 컵을 두 수의 쌍으로 나타내자. 쌍 $(l, t)$는 온도 $t$ Bytesius 도인 $l$ bitre의 차가 담긴 컵을 뜻한다.

첫 번째 테스트케이스에서 Bytekids는 컵 $(2, 1)$과 $(2, 5)$를 가진다. 차 나누기 연산으로 컵 $(\frac12, 1)$, $(\frac32, 1)$, $(\frac12, 5)$, $(\frac32, 5)$를 얻을 수 있다.

그다음 컵 $(\frac12, 1)$과 $(\frac32, 5)$를 섞으면 $\tfrac12 + \tfrac32 = 2$ bitre이고 온도가

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

인 차, 즉 컵 $(2,4)$를 얻는다. 마찬가지로 컵 $(\frac32, 1)$과 $(\frac12, 5)$를 섞으면 $(2, 2)$를 얻는다. 결국 Bytekids는 알맞은 양과 온도의 차가 담긴 컵 두 개를 갖게 된다.

두 번째 테스트케이스에서는 두 차 모두 너무 뜨겁다. 여기서는 별로 할 수 있는 게 없다.

세 번째 테스트케이스에서는 Bytekids가 컵을 맞바꾸기만 하면 된다.