1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

struct Rect {
	int l,a,b;
	bool operator < (const Rect&R) const {
		return a>R.a;
	}
};

const int nax = 100*1000+10;
int t,n;
Rect rect[nax];
Rect rect2[nax];

int main() {_
	cin>>t;
	while(t--) {
		cin>>n;
		for(int i=1; i<=n; i++) {
			cin>>rect[i].l>>rect[i].a>>rect[i].b;
			rect2[i].l=rect[i].l;
			rect2[i].a=rect[i].b;
		}
		sort(rect+1,rect+1+n);
		sort(rect2+1,rect2+1+n);
		ll tot_l = 0,tot_p=0,L=0,R=0,lenL=0,lenR=0;
		int wsk1=0,wsk2=n+1;
		bool ans = 1;
		for(int i=1; i<=n; i++) {
			tot_l+=rect2[i].l;
			tot_p+=(ll)rect2[i].l*rect2[i].a;
			while(wsk1+1<=n&&lenL+rect[wsk1+1].l<=tot_l) {
				lenL+=rect[wsk1+1].l;
				L+=(ll)rect[wsk1+1].a*rect[wsk1+1].l;
				wsk1++;
			}
			while(wsk2-1>=1&&lenR+rect[wsk2-1].l<=tot_l) {
				lenR+=rect[wsk2-1].l;
				R+=(ll)rect[wsk2-1].a*rect[wsk2-1].l;
				wsk2--;
			}
			L+=(ll)(tot_l-lenL)*rect[wsk1+1].a;
			R+=(ll)(tot_l-lenR)*rect[wsk2-1].a;
			if(tot_p>L) {
				ans=0;
			}
			L-=(ll)(tot_l-lenL)*rect[wsk1+1].a;
			R-=(ll)(tot_l-lenR)*rect[wsk2-1].a;
		}
		if(tot_p!=L) ans=0;
		if(ans) cout<<"TAK\n";
		else cout<<"NIE\n";
	}
			
	
}