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
#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;
using ll = long long;

#define X first
#define Y second

int t, n;
vector<ii> A, B;

int main() {
	scanf("%d", &t);
	while(t--) {
		int n;
		scanf("%d", &n);
		A.resize(n);
		B.resize(n);
		
		ll sa = 0, sb = 0;
		for(int i = 0 ; i < n ; i++) {
			int l, a, b;
			scanf("%d%d%d", &l, &a, &b);
			A[i] = {a, l};
			B[i] = {b, l};
			sa += ll(a) * ll(l);
			sb += ll(b) * ll(l);
		}
		
		if(sa != sb) {
			printf("NIE\n");
			continue;
		}
		
		sort(A.begin(), A.end());
		sort(B.begin(), B.end());
		
		int i = 0, j = 0;
		vector<ll> hlp;
		while(i < n) {
			if(i < n && A[i].Y == 0) i++;
			if(j < n && B[j].Y == 0) j++;
			
			if(i == n)
				break;
				
			int l = min(A[i].Y, B[j].Y);
			hlp.push_back(ll(l) * ll(B[j].X - A[i].X));
			A[i].Y -= l;
			B[j].Y -= l;
		}
		
		ll sum = 0;
		bool wowowo = false;
		for(ll x : hlp) {
			if(x > 0)
				sum += x;
			if(x < 0) {
				if(sum + x < 0) {
					wowowo = true;
					break;
				}
				sum += x;
			}
		}
		
		if(wowowo)
			printf("NIE\n");
		else
			printf("TAK\n");
	}
	return 0;
}