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
95
96
97
98
#include <iostream>
#include <algorithm>

using namespace std;

pair<int, int> pa[100001], pb[100001];
int n;

bool daSie()
{
    sort(pa, pa+n);
    sort(pb, pb+n);

    long long nad=0;
    int wskA=n-1, zostA=pa[wskA].second;

    for (int i=n-1; 0<=i; --i)
    {
        int l=pb[i].second;
        while (l)
        {
            int wz=min(l, zostA);
            nad+=pa[wskA].first*(long long) wz;
            l-=wz;
            zostA-=wz;
            if (zostA==0)
            {
                --wskA;
                zostA= wskA<0 ? 0 : pa[wskA].second;
            }
        }

        nad-=pb[i].first*(long long) pb[i].second;
        if (nad<0)
            return false;
    }

    return nad==0;
}

bool daSie2()
{
//    for (int i=0; i<n; ++i)
//    {
//        pa[i].first=1000000-pa[i].first;
//        pb[i].first=1000000-pb[i].first;
//    }
//    return daSie();

    long long nad=0;
   int wskA=0, zostA=pa[wskA].second;

   for (int i=0; i<n; ++i)
   {
       int l=pb[i].second;
       while (l)
       {
           int wz=min(l, zostA);
           nad+=pa[wskA].first*(long long) wz;
           l-=wz;
           zostA-=wz;
           if (zostA==0)
           {
               ++wskA;
               zostA=pa[wskA].second;
           }
       }

       nad-=pb[i].first*(long long) pb[i].second;
       if (0<nad)
           return false;
   }

   return nad==0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    int t;
    cin>>t;
    for (; 0<t; --t)
    {
        cin>>n;
        for (int i=0; i<n; ++i)
        {
            int l, a, b;
            cin>>l>>a>>b;
            pa[i].first=a;
            pa[i].second=l;
            pb[i].first=b;
            pb[i].second=l;
        }
        cout<<(daSie() && daSie2() ? "TAK\n" : "NIE\n");
    }

    return 0;
}