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

bool her(void)
{
    int n;
    long long sa = 0LL, sb = 0LL;
    std::map<int, int> A, B;

    scanf("%d\n", &n);

    for (int i = 0; i < n; i++) {
        int l, a, b;

        scanf("%d%d%d", &l, &a, &b);
        A[a] += l;
        B[b] += l;
        sa += static_cast<long long>(l) * static_cast<long long>(a);
        sb += static_cast<long long>(l) * static_cast<long long>(b);
    }

    if (sa != sb)
        return 0;

    auto iA = A.begin();
    long long na = 0LL, nb = 0LL;

    sa = sb = 0LL;

    for (auto iB = B.begin(); iB != B.end(); ++iB) {
        nb += iB->second;
        sb += iB->first * iB->second;

        while (na < nb) {
            long long d = nb - na;

            if (iA->second <= d) {
                na += iA->second;
                sa += static_cast<long long>(iA->first) * static_cast<long long>(iA->second);
                iA->second = 0;
                ++iA;
            }
            else {
                na += d;
                sa += static_cast<long long>(iA->first) * d;
                iA->second -= d;
            }
        }

        if (sa > sb)
            return 0;
    }

    return 1;
}

int main(void)
{
    int i, t;

    scanf("%d", &t);

    for (i = 0; i < t; i++)
        printf("%s\n", her() ? "TAK" : "NIE");

    return 0;
}