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

typedef long long ll;

int t, n, k, l;
ll sum_a, sum_b, a, b, c, x, y;
std::vector<std::pair<ll, ll>> va, vb;

bool solve() {
    va.clear();
    vb.clear();

    scanf("%d", &n);

    sum_a = sum_b = 0;

    for (int i = 0; i < n; ++i) {
        scanf("%lld%lld%lld", &a, &b, &c);
        va.push_back({b, a});
        vb.push_back({c, a});
        sum_a += b * a;
        sum_b += c * a;
    }

    if (sum_a != sum_b)
        return false;

    std::sort(va.begin(), va.end());
    std::sort(vb.begin(), vb.end());

    if (va[0].first > vb[0].first || va.back().first < vb.back().first)
        return false;

    k = l = 0;
    x = y = 0;
    sum_a = sum_b = 0;

    while (k < n && l < n) {
        if (x + va[k].second <= y + vb[l].second) {
            x += va[k].second;
            y += va[k].second;

            sum_a += va[k].first * va[k].second;
            sum_b += vb[l].first * va[k].second;

            vb[l].second -= va[k].second;

            ++k;
            if (vb[l].second == 0) ++l;            
        }
        else {
            x += vb[l].second;
            y += vb[l].second;

            sum_a += va[k].first * vb[l].second;
            sum_b += vb[l].first * vb[l].second;

            va[k].second -= vb[l].second;

            ++l;
            if (va[k].second == 0) ++k;
        }

        if (sum_a > sum_b)
            return false;
    }
    return true;
}

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