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
#include <algorithm>
#include <cstdio>

using namespace std;
typedef long long LL;

const int N = 1e5 + 1;

pair<LL, LL> at[N];
pair<LL, LL> bt[N];
pair<LL, LL> atp[2 * N];
pair<LL, LL> btp[2 * N];

void solve() {
    int n = 0;
    LL l, a, b;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld %lld %lld", &l, &a, &b);
        at[i].second = bt[i].second = l;
        at[i].first = a;
        bt[i].first = b;
    }
    sort(at, at + n);
    sort(bt, bt + n);
    int ia = 0, ib = 0;
    int ac = 0, bc = 0;
    while (ia < n && ib < n) {
        if (at[ia].second == bt[ib].second) {
            atp[ac++] = at[ia];
            btp[bc++] = bt[ib];
            ++ia, ++ib;
        } else if (at[ia].second < bt[ib].second) {
            atp[ac++] = at[ia];
            btp[bc].first = bt[ib].first;
            btp[bc++].second = at[ia].second;
            bt[ib].second -= at[ia].second;
            ++ia;
        } else {
            btp[bc++] = bt[ib];
            atp[ac].first = at[ia].first;
            atp[ac++].second = bt[ib].second;
            at[ia].second -= bt[ib].second;
            ++ib;
        }
    }
    if (ia < n) {
        atp[ac++] = at[ia];
    }
    if (ib < n) {
        btp[bc++] = bt[ib];
    }

    LL sum1 = 0, sum2 = 0;
    for (int i = 0; i < ac; ++i) {
        sum1 += atp[i].first * atp[i].second;
        sum2 += btp[i].first * btp[i].second;
        if (sum1 > sum2) {
            printf("NIE\n");
            return;
        }
    }
    sum1 = 0;
    sum2 = 0;
    for (int i = ac - 1; i >= 0; --i) {
        sum1 += atp[i].first * atp[i].second;
        sum2 += btp[i].first * btp[i].second;
        if (sum1 < sum2) {
            printf("NIE\n");
            return;
        }
    }
    printf("TAK\n");
    return;
}

int main() {
    int t = 0;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
}