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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
typedef pair <int,LL> il;
typedef pair <int,double> id;
#define pb push_back
const int INF = 2147483647;
const int N = 100005;
const double eps = 1e-9;

int z, n, i, l, a, b;
vector<il> v1, v2;
LL sum1, sum2;
map<int, LL> mapa;
set<id> s1, s2;

bool ok() {
	s1.clear();
	s2.clear();
	id w1, w2, w3;
	double a1, a2, d, p;
	set<id>::iterator it;
	for (auto& w : mapa) if (w.second > 0) s1.insert(id(w.first, w.second * 1.0)); else if (w.second < 0) s2.insert(id(w.first, w.second * -1.0)); 
	//for (auto& w : s1) printf("%d %.3lf\n", w.first, w.second); printf("\n");
	//for (auto& w : s2) printf("%d %.3lf\n", w.first, w.second); printf("\n");
	while (s1.size() > 0) {
		w1 = *s1.begin();
		s1.erase(s1.begin());
		w2 = *s2.begin();
		s2.erase(s2.begin());
		//printf("%d %.3lf %d %.3lf\n", w1.first, w1.second, w2.first, w2.second);
		if (w1.first > w2.first) return false;
		it = s1.upper_bound(id(w2.first, numeric_limits<double>::max()));
		if (it == s1.end()) return false;
		w3 = *it;
		s1.erase(it);
		//printf("%d %.3lf %d %.3lf %d %.3lf\n", w1.first, w1.second, w2.first, w2.second, w3.first, w3.second);
		p = (w2.first - w1.first) * 1.0 / (w3.first - w2.first);
		if (w3.second < p * w1.second) {
			a1 = 1 / p * w3.second;
			a2 = w3.second;
		} else {
			a1 = w1.second;
			a2 = p * w1.second;
		}
		d = min(1.0, w2.second / (a1 + a2));
		a1 *= d;
		a2 *= d;
		w1.second -= a1;
		w2.second -= (a1 + a2);
		w3.second -= a2;
		if (w1.second > eps) s1.insert(w1);
		if (w2.second > eps) s2.insert(w2);
		if (w3.second > eps) s1.insert(w3);
	}
	return true;
}

int main() {
scanf("%d", &z);
while(z--) {
	scanf("%d", &n);
	sum1 = 0; 
	sum2 = 0;
	mapa.clear();
	for (i=0;i<n;i++) {
		scanf("%d %d %d", &l, &a, &b);
		mapa[a] += l;
		mapa[b] -= l;
		sum1 += a * 1LL * l;
		sum2 += b * 1LL * l;
	}
	if (sum1 != sum2) {
		printf("NIE\n");
		continue;
	}
	if (ok()) printf("TAK\n"); else printf("NIE\n");
}
return 0;
}