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
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n;
	long double min1 = 1000010, max1 = 0, min2 = 1000010, max2 = 0;
	long double sum1 = 0, sum2 = 0;
	cin >> n;
	vector<long double> v(n + 3), x(n + 3), y(n + 3), need(n + 1);
	vector<pair<int, int>> tab, tab2;
	for (int a = 1; a <= n; a++) {
		cin >> v[a] >> x[a] >> y[a];
		sum1 += v[a] * x[a];
		sum2 += v[a] * y[a];
		
		if (x[a] < y[a]) {
			tab.push_back({-y[a], a});
		}
		
		if (y[a] < x[a]) {
			tab2.push_back({-x[a], a});
		}

		min1 = min(min1, x[a]);
		max1 = max(max1, x[a]);
		min2 = min(min2, y[a]);
		max2 = max(max2, y[a]);
	}

	if (sum1 == sum2 && min1 <= min2 && max2 <= max1) {
		sort(tab.begin(), tab.end());
		sort(tab2.begin(), tab2.end());

		int ptr = 0;

		for (int a = 0; a < tab.size(); a++) {
			int id = tab[a].second;
			int id2 = tab2[ptr].second;

			need[id] = v[id] * (y[id] - x[id]);

			while (need[id]) {
				if (v[id] == 0) {
					cout << "NIE" << endl;
					return;
				}
				
				if (ptr >= tab2.size()) {
					cout << "NIE" << endl;
					return;
				}

				id2 = tab2[ptr].second;

				long double diff = x[id2] - x[id];
				long double flow = need[id] / diff;

				flow = min(flow, v[id]);
				flow = min(flow, v[id2]);
				
				// cout << id << " " << need[id] << " " << flow << endl;

				need[id] -= flow * diff;
				v[id] -= flow;
				v[id2] -= flow;

				if (v[id2] == 0) ptr++;
			}
		}

		for (int a = 0; a < tab.size(); a++) {
			if (need[tab[a].second]) {
				cout << "NIE" << endl;
				return;
			}
		}

		cout << "TAK" << endl;
	}
	else {
		cout << "NIE" << endl;
	}
}

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

	int t;
	cin >> t;
	while (t--) {
		solve();
	}


	return 0;
}