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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef long long ll;

int t, n;
ll a[111111][2], b[111111][2];

int cmp(const void *av, const void *bv) {
    ll *a = (ll *)av;
    ll *b = (ll *)bv;
    return a[1] - b[1];
}


int main()
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        ll sum = 0;
        for (int i=0; i<n; i++) {
            ll l, aa, bb;
            scanf("%lld %lld %lld", &l, &aa, &bb);
            a[i][0] = l;
            a[i][1] = aa;

            b[i][0] = l;
            b[i][1] = bb;
            
            sum += l*aa - l*bb;
        }

        if (sum != 0) {
            printf("NIE\n");
        } else {
            qsort(a, n, sizeof(a[0]), cmp);
            qsort(b, n, sizeof(a[0]), cmp);
            ll la=0, ma=0, wyzn;
            ll lb=b[0][0]*b[0][1], mb=b[0][0];
            int pa=0, pb=1;
            while (1) {
                while ((wyzn = la*mb - lb*ma) <= 0 && pa < n) {
                    //printf("wyzn=%lld\n", wyzn);
                    la += a[pa][0]*a[pa][1];
                    ma += a[pa][0];
                    pa ++;
                }

                if (wyzn >=0 && ma >= mb && pb < n) {
                    la -= lb;
                    ma -= mb;

                    lb = b[pb][0]*b[pb][1];
                    mb = b[pb][0];
                    pb ++;
                } else {
                    break;
                }
            }
            if (pa == n && pb == n) {
                printf("TAK\n");
            } else {
                printf("NIE\n");
            }
        }
    }

    return 0;
}