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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

using namespace std;

long long x[2000000][2], p[2000000][2], k[2000000][2], w[2000000][2];


int war(const void* aa, const void* bb)
{
    if(*(long long*)aa>*(long long*)bb)return (1);
    return(-1);
}

int main()
{
    long long n, q, t, a, b, i, j, s;

    scanf("%lld", &t);

    for(q=0; q<t; q++)
    {
        scanf("%lld", &n);
        for(i=0; i<n; i++)
        {
            scanf("%lld%lld%lld", &x[i][1], &x[i][0], &w[i][0]);
            w[i][1]=x[i][1];
        }
        qsort(x, n, 16, war);
        qsort(w, n, 16, war);
/*        printf("\n");
        for(i=0; i<n; i++)
        {
            printf("%lld %lld\n", x[i][1], x[i][0]);
        }
        printf("\n");
        for(i=0; i<n; i++)
        {
            printf("%lld %lld\n", w[i][1], w[i][0]);
        }
        printf("\n");
*/        p[0][0]=0;
        p[0][1]=0;
        k[n][0]=0;
        k[n][1]=0;
        for(i=0; i<n; i++)
        {
            p[i+1][0]=x[i][0]*x[i][1]+p[i][0];
            p[i+1][1]=x[i][1]+p[i][1];
            k[n-1-i][0]=x[n-1-i][0]*x[n-1-i][1]+k[n-i][0];
            k[n-1-i][1]=x[n-1-i][1]+k[n-i][1];
        }
/*        for(i=0; i<=n; i++)
        {
            printf("%lld %lld\n", p[i][1], p[i][0]);
        }
        for(i=0; i<=n; i++)
        {
            printf("%lld %lld\n", k[i][1], k[i][0]);
        }
        printf("\n\n\n");
*/
        s=1;

        j=0;
        a=0;
        b=0;

        for(i=0; i<n; i++)
        {
            a+=w[i][0]*w[i][1];
            b+=w[i][1];
            while(p[j+1][1]<b)j++;
//            printf("%lld %lld\n", p[j][0]+(b-p[j][1])*x[j][0], b);
            if(p[j][0]+(b-p[j][1])*x[j][0]>a)s=0;
        }

        j=n;
        a=0;
        b=0;

        for(i=n-1; i>=0; i--)
        {
            a+=w[i][0]*w[i][1];
            b+=w[i][1];
            while(k[j-1][1]<b)j--;
            if(k[j][0]+(b-k[j][1])*x[j-1][0]<a)s=0;
        }

        if(s==1)printf("TAK\n");
        else printf("NIE\n");
    }

    return 0;
}