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
#include <algorithm>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>

template<class ForwardIt1, class ForwardIt2, class Comp>
bool solve(ForwardIt1 a, ForwardIt1 aend, ForwardIt2 b, ForwardIt2 bend, Comp comp) {
	long long prev_at = 0;
	long long prev_av = 0;
	long long t = 0;
	for (; b != bend; ++b) {
		const auto& [bt, bv] = *b;
		long long v = 0;
		long long add = std::min(prev_av, bv);
		v += add;
		t += prev_at * add;
		prev_av -= add;
		for (; v < bv; ++a) {
			const auto& [at, av] = *a;
			prev_at = at;
			prev_av = av;
			long long add = std::min(av, bv - v);
			v += add;
			t += prev_at * add;
			prev_av -= add;
		}
		if (comp(bt * bv, t))
			return false;
		t -= bt * bv;
	}
	return true;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t;
	std::cin >> t;
	while (t--) {
		int n;
		std::cin >> n;
		std::vector<std::pair<int, long long>> ma, mb;
		for (int i = 0; i < n; i++) {
			int d, a, b;
			std::cin >> d >> a >> b;
			ma.emplace_back(a, d);
			mb.emplace_back(b, d);
		}
		std::sort(ma.begin(), ma.end());
		std::sort(mb.begin(), mb.end());
		std::cout << (
			solve(ma.begin(), ma.end(), mb.begin(), mb.end(), std::less<> {}) &&
			solve(ma.rbegin(), ma.rend(), mb.rbegin(), mb.rend(), std::greater<> {}) ?
		"TAK\n" : "NIE\n");
	}
	return 0;
}