절대라는 말은 절대 하지 마

"도대체 직원들 급여를 어떻게 정해야 하지?" 카리에로비치 사장은 고민했다. "모두에게 효율에 비례해 급여를 주고 싶어. 하지만 직원들의 효율은 계속 변하고, 게다가 우리 회사에 효율이 완전히 똑같은 두 직원이 동시에 있는 일은 절대 없을 거야."

그로부터 오랜 세월이 흘렀다. 그동안 사장의 회사를 거쳐 간 직원은 모두 $N$명이다. $i$번째 직원은 네 정수 $s_i$, $e_i$, $a_i$, $b_i$로 나타난다. 이 직원은 시각 $s_i$에 입사해 시각 $e_i$에 퇴사했으며(혹은 회사가 그를 내보냈으며), 임의의 시각 $t$에서의 효율은 $a_i \cdot t + b_i$이다.

회사의 역사에서, 그 순간에 동시에 재직 중이던 두 직원의 효율이 정확히 같아지는 순간이 한 번이라도 있었는지 판정하라.

• $a_i$는 음수일 수 있다.
• 효율은 음수일 수 있다(이익을 내기는커녕 회사에 손해를 끼치는 경우에 해당한다).
• 각 재직 구간 $[s_i, e_i]$는 양 끝을 포함하며, 정수뿐 아니라 모든 실수 시각 $t$를 고려해야 한다.

첫째 줄에 테스트 집합의 개수를 나타내는 정수 $Z$ ($1 \le Z \le 10$)가 주어진다. 이어서 각 테스트 집합이 주어진다.

각 테스트 집합의 첫째 줄에는 회사의 역사에 등장한 직원 수를 나타내는 정수 $N$ ($1 \le N \le 10^5$)이 주어진다. 이어지는 $N$개의 줄에는 각각 공백으로 구분된 네 정수 $s_i$, $e_i$, $a_i$, $b_i$가 주어진다. 여기서 $0 \le s_i, e_i \le 10^6$이고 $-10^6 \le a_i, b_i \le 10^6$이다.

각 테스트 집합마다, 동시에 재직 중이던 어떤 두 직원의 효율이 같아지는 순간이 존재하면 "TAK"를, 그렇지 않으면 "NIE"를 한 줄에 하나씩 출력한다.