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

using namespace std;

struct mug {
    int l;
    int t;
};

int n;

mug a[100000];
mug b[100000];

bool mug_compare(mug lhs, mug rhs) {
    return lhs.t < rhs.t;
}

bool check_set() {
    long long c = 0L;
    int i, j, l;
    for (i=0, j=0, l=0; i<n; i++) {
        while (j<n && l < b[i].l) {
            if (l + a[j].l <= b[i].l) {
                l += a[j].l;
                c += a[j].l * a[j].t;
                j++;
            } else {
                int dl = b[i].l - l;
                l += dl;
                c += dl * a[j].t;
                a[j].l -= dl;
            }
        }
        if (l != b[i].l || l * b[i].t < c)
            return false;
        c -= l * b[i].t;
        l = 0;
    }
    if (j != n || c != 0)
        return false;
    return true;
}

main() {
    int t;
    cin >> t;
    for (int i=0; i<t; i++) {
        cin >> n;
        for (int j=0; j<n; j++) {
            cin >> a[j].l >> a[j].t >> b[j].t;
            b[j].l = a[j].l;
        }
        sort(a, a + n, mug_compare);
        sort(b, b + n, mug_compare);
        if (check_set())
            cout << "TAK" << endl;
        else
            cout << "NIE" << endl;
    }
    return 0;
}