재미있는 정보학 대회

이 문제의 주인공 Olgierd는 여러분과 같은 고등학생입니다. 폴란드 정보 올림피아드 결선에 진출하기 위해 여러 온라인 사이트에서 문제를 풀며 연습하고 있습니다.

다음 준비 단계는 재미있는 정보학 대회(ŚKI)입니다. 이 대회는 여러 개의 라운드로 이루어져 있고, 라운드들의 진행 시간 구간은 서로 자유롭게 겹칠 수 있습니다. 각 라운드마다 문제가 하나씩 출제됩니다.

Olgierd는 아직 문제를 알지 못하지만, 각 라운드에 몇 시간을 쓸지는 이미 정해 두었습니다. 한 번 어떤 문제를 붙잡으면 정해 둔 시간 동안 중간에 쉬지 않고 그 문제만 계속 풉니다(카페인의 힘). 규칙은 다음과 같습니다.

• 한 순간에는 한 문제만 풀 수 있습니다.
• 어떤 라운드의 문제는 그 라운드가 시작되기 전에는 시작할 수 없고(문제를 아직 모르므로), 그 라운드가 끝난 뒤에는 풀지 않습니다.
• 문제는 정해 둔 시간만큼 한 번에 이어서 풉니다(중간에 나눌 수 없습니다).

ŚKI의 문제는 매우 어렵기 때문에, Olgierd가 각 라운드에 쓰기로 한 시간은 그 라운드 전체 길이의 절반 이상입니다.

모든 라운드에 정확히 계획한 만큼의 시간을 쓸 수 있도록 일정을 짤 수 있는지 판단해 주세요.

정리하면, 라운드가 $n$개 있습니다. $i$번째 라운드는 시간 구간 $[a_i, b_i]$ 안에서 진행됩니다. Olgierd는 이 라운드에 길이 $c_i$의 연속된 시간을 쓰려 하며, 이 작업 구간은 반드시 $[a_i, b_i]$ 안에 완전히 들어가야 합니다. 서로 다른 라운드의 작업 구간은 시간상 겹칠 수 없습니다(경계에서 맞닿는 것은 허용). 모든 라운드에 대해 $\frac{b_i - a_i}{2} \le c_i$ 임이 보장됩니다. 이렇게 겹치지 않는 배치가 존재하는지 판단하세요.

첫째 줄에 데이터 집합(테스트 케이스)의 개수 $z$가 주어집니다.

각 데이터 집합의 첫째 줄에는 라운드의 개수 $n$ ($1 \le n \le 2 \cdot 10^5$)이 주어집니다. 이어서 $n$개의 줄에 각 라운드의 정보가 세 정수 $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$)로 주어집니다. 이는 $i$번째 라운드가 시각 $a_i$에 시작하여 시각 $b_i$에 끝나고, Olgierd가 이 라운드에 $c_i$만큼의 시간을 쓰려 한다는 뜻입니다. 모든 데이터 집합에 걸친 $n$의 합은 $10^6$을 넘지 않습니다.

각 데이터 집합마다 한 줄에, Olgierd가 계획을 실현할 수 있으면 TAK을, 불가능하면 NIE를 출력합니다. (TAK은 "예", NIE는 "아니오"를 뜻합니다.)