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
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define PPC(x) __builtin_popcountll((x))
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define st first
#define nd second
using namespace std;

const int maxN = 1 << 18, maxA = 1 << 20;

long long prod[maxN], ile[maxA];
int End[maxN];
bool pres[maxA];
vector <int> kto, Plus, Minus;

void clear()
{
	for (int a : kto)
		ile[a] = 0ll, pres[a] = false;
	kto.resize(0);
	Minus.resize(0);
	Plus.resize(0);
}

inline long long align(long long& a, long long& b)
{
	long long c = min(a, b);
	a -= c;
	b -= c;
	return c;
}

bool solve()
{
	clear();
	int n;
	scanf ("%d", &n);
	while (n--)
	{
		int l, a, b;
		scanf ("%d%d%d", &l, &a, &b);
		for (int c : {a, b})
			if (!pres[c])
				kto.pb(c), pres[c] = true;
		ile[a] += l;
		ile[b] -= l;
	}
	
	for (int a : kto)
	{
		if (ile[a] > 0ll)
			Plus.pb(a);
		if (ile[a] < 0ll)
			Minus.pb(a), ile[a] *= -1ll;
	}
	sort(ALL(Plus));
	sort(ALL(Minus));
	int qb = 0, qe = 0, ip = 0, im = 0;
	
	while (ip < Plus.size())
	{
		assert(im < Minus.size());
		int a = Plus[ip], b = Minus[im];
		long long p = align(ile[a], ile[b]) * abs(b - a);
		
		if (ile[a] == 0ll)	ip++;
		if (ile[b] == 0ll)	im++;
		if (a < b)
		{
			prod[qe] = p;
			End[qe++] = b;
		}

		else while (p != 0ll)
		{
			if (qe == qb or End[qb] > b)
				return false;
			align(p, prod[qb]);
			if (prod[qb] == 0ll)
				qb++;
		}
	}
	
	return qe == qb;
}

int main()
{
	int t;
	scanf ("%d", &t);
	while (t--)
		printf("%s\n", solve() ? "TAK" : "NIE");
	return 0;
}