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
#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while(t --> 0) {
		int n;
		cin >> n;
		vector<pair<int, int>> A, B;
		while(n --> 0) {
			int l, a, b;
			cin >> l >> a >> b;
			A.emplace_back(a, l);
			B.emplace_back(b, l);
		}
		auto output = [&] {
			sort(A.begin(), A.end());
			sort(B.begin(), B.end());
			LL arrow_sum = 0;
			while(A.size() or B.size()) {
				if(A.size() and A.back().second == 0) {
					A.pop_back();
					continue;
				}
				if(B.size() and B.back().second == 0) {
					B.pop_back();
					continue;
				}
				int a = A.back().first, b = B.back().first, l = min(A.back().second, B.back().second);
				A.back().second -= l;
				B.back().second -= l;
				arrow_sum += l * LL(a - b);
				if(arrow_sum < 0)
					return false;
			}
			if(A.size() or B.size() or arrow_sum)
				return false;
			return true;
		};
		if(output())
			cout << "TAK\n";
		else
			cout << "NIE\n";
	}
}