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 #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 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; }