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
#include <bits/stdc++.h>
using namespace std;

int T, N, l, a, b;

vector<pair<int, int>> av, bv;
long long al, bl;
int ai, bi;

void solve() {
    scanf("%d", &N);
    av.resize(N); av.clear();
    bv.resize(N); bv.clear();

    al = bl = 0LL;
    for (int i = 0; i < N; ++i) {
        scanf("%d %d %d", &l, &a, &b);
        av.push_back(make_pair(a, l));
        bv.push_back(make_pair(b, l));
        al += a * l;
        bl += b * l;
    }

    if (al != bl) {
        printf("NIE\n");
        return;
    }

    sort(av.begin(), av.end());
    sort(bv.begin(), bv.end());

    ai = bi = 0;
    while (bi < N) {
        bl -= bv[bi].first * bv[bi].second;
        while (bv[bi].second > 0) {
            if (av[ai].second < bv[bi].second) {
                al -= av[ai].first * av[ai].second;
                bv[bi].second -= av[ai].second;
                av[ai].second = 0;
                ai++;
            } else {
                al -= av[ai].first * bv[bi].second;
                av[ai].second -= bv[bi].second;
                bv[bi].second = 0;
                if (av[ai].second == 0) {
                    ai++;
                }
            }
        }
        if (al < bl) {
            printf("NIE\n");
            return;
        }
        bi++;
    }
    printf("TAK\n");
}

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