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
// Karol Kosinski 2019
#include <cstdio>
#include <algorithm>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
//#define DEBUG(x...) printf(x)
#define DEBUG(x...)
using namespace std;

typedef long long LL;
const int NN = 100002;
const int MX = 1'000'001;

int A[NN], B[NN];
LL CA[MX], CB[MX];

void clear(int ia, int ib)
{
    FOR(i,0,ia) CA[A[i]] = 0;
    FOR(i,0,ib) CB[B[i]] = 0;
}

bool check(int na, int nb)
{
    LL sum_a = 0, sum_b = 0;
    int ia = 0, ib = 0;
    while (ia < na)
    {
        LL &part_a = CA[A[ia]];
        LL &part_b = CB[B[ib]];
        DEBUG("(ia, part_a, A[ia], sum_a) = "
                "%3d, %3lld, %3d, %3lld    ",
                ia, part_a, A[ia], sum_a);
        DEBUG("(ib, part_b, B[ib], sum_b) = "
                "%3d, %3lld, %3d, %3lld\n",
                ib, part_b, B[ib], sum_b);
        LL min_part = min(part_a, part_b);
        sum_a += min_part * A[ia];
        sum_b += min_part * B[ib];
        part_a -= min_part;
        part_b -= min_part;
        if (part_a == 0) ++ia;
        if (part_b == 0) ++ib;
        if (sum_a > sum_b) return false;
    }
    return sum_a == sum_b;
}

bool testcase()
{
    int n, ia = 0, ib = 0;
    scanf("%d", &n);
    FOR(i,0,n)
    {
        int l, a, b;
        scanf("%d%d%d", &l, &a, &b);
        if (CA[a] == 0) A[ia++] = a;
        if (CB[b] == 0) B[ib++] = b;
        CA[a] += l;
        CB[b] += l;
    }
    sort(A, A + ia);
    sort(B, B + ib);
    bool res = check(ia, ib);
    clear(ia, ib);
    return res;
}

int main()
{
    int z;
    scanf("%d", &z);
    while (z--) printf(testcase() ? "TAK\n" : "NIE\n");
    return 0;
}