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
#include <bits/stdc++.h>
#define booost ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define fi first
#define se second
using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair < int, int > PII;
typedef pair < LL, LL > PLL;
typedef pair < LD, LD > PDD;

const LL MOD=1e9+7;
const LL LLINF=1e18+7;
vector<PII> pocz,kon;
int main()
{
    //booost;
    //freopen("C:/Users/kucha/Documents/ISIM 5. semestr/PA/tests/MS5.in","r",stdin);
    int t,n,l,a,b;
    scanf("%d", &t);
    int cnt=0;
    while(t--)
    {
        pocz.clear();
        kon.clear();
        scanf("%d",&n);
        bool ok=true;
        LL sum1=0,sum2=0,summ=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d %d %d",&l,&a,&b);
            sum1+=l*(LL)a;
            sum2+=l*(LL)b;
            pocz.push_back({a,l});
            kon.push_back({b,l});
        }
        if(sum1!=sum2)
        {
            printf("NIE\n");
            continue;
        }
        sort(pocz.begin(),pocz.end());
        sort(kon.begin(),kon.end());
        deque<PLL> q1,q2;
        for(int i=0;i<n;i++)
        {
            q1.push_back(pocz[i]);
            q2.push_back(kon[i]);
        }
        summ=0;
        while(!q1.empty() && !q2.empty())
        {
            PLL el1=q1.back(),el2=q2.back();
            q1.pop_back();
            q2.pop_back();

            if(el1.se==el2.se)
            {
                summ+=el2.se*(el2.fi-el1.fi);
            }
            else if(el1.se<el2.se)
            {
                summ+=el1.se*(el2.fi-el1.fi);
                q2.push_back({el2.fi,el2.se-el1.se});
            }
            else
            {
                summ+=el2.se*(el2.fi-el1.fi);
                q1.push_back({el1.fi,el1.se-el2.se});
            }
            if(summ>0)
            {
                ok=false;
            }
        }
        if(summ!=0)
        {
            ok=false;
        }
        if(ok)
        {
            printf("TAK\n");
            cnt++;
        }
        else
        {
            printf("NIE\n");
        }
    }
    //cout<<cnt<<'\n';
}