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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

#define st first
#define nd second
#define PII pair <int, int>

const int N = 1e5 + 7;

int n;
int l[N], a[N], b[N];

bool ok(vector <PII> fa, vector <PII> fb){
	reverse(fa.begin(), fa.end());
	reverse(fb.begin(), fb.end());

	LL bal = 0;
	while(fa.size() && fb.size()){
		auto ta = fa.back();
		auto tb = fb.back();
		
		fa.pop_back();
		fb.pop_back();

		int sz = min(ta.nd, tb.nd);
		bal += 1LL * sz * (tb.st - ta.st);
		
		if(bal < 0)
			return false;
		
		ta.nd -= sz;
		tb.nd -= sz;
		
		if(ta.nd)
			fa.push_back(ta);
		if(tb.nd)
			fb.push_back(tb);
	}
	
	return bal == 0;
}

bool check(){
	LL bal = 0;
	vector <pair <int, int> > cur;
	vector <pair <int, int> > cur2;
	
	for(int i = 1; i <= n; ++i){
		bal += 1LL * l[i] * (a[i] - b[i]);
		cur.push_back({a[i], l[i]});
		cur2.push_back({b[i], l[i]});
	}
	
	if(bal != 0)
		return false;
	
	sort(cur.begin(), cur.end());	
	sort(cur2.begin(), cur2.end());
	
	if(!ok(cur, cur2))
		return false;
	
	reverse(cur.begin(), cur.end());
	reverse(cur2.begin(), cur2.end());
	
	if(!ok(cur2, cur))
		return false;
	return true;
}

void solve(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d %d %d", &l[i], &a[i], &b[i]);
	puts(check() ? "TAK" : "NIE");
}

int main(){
	int cases;
	scanf("%d", &cases);
	
	while(cases--)
		solve();
	return 0;
}