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>
#define fi first
#define sc second
#define mp make_pair
#define pb push_back
#define forn(I,P,K) for(int (I)=(P);(I)<=(K);++(I))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld,ld> para;
const ld eps=0.0000001;
vector<para> A,B;
queue<para> Q;

inline int solve()
{
    A.clear();
    B.clear();
    while(!Q.empty())   Q.pop();
    int n;
    ll ax=0,bx=0;
    cin>>n;
    forn(i,1,n)
    {
        int l,a,b;
        cin>>l>>a>>b;
        A.pb({a,l});
        B.pb({b,l});
        ax+=1LL*a*l;
        bx+=1LL*b*l;
    }
    if(ax!=bx)  return cout<<"NIE\n",0;
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    int ind=0;
    for(auto &v:B)
    {
        while(ind<(int)A.size()&&A[ind].fi<=v.fi+eps)
        {
            Q.push(A[ind]);
            ind++;
        }
        while(v.sc>eps)
        {
            if(Q.empty())       return cout<<"NIE\n",0;
            auto x=Q.front();
            Q.pop();
            para y;
            if(ind>=(int)A.size())   y=mp(0,0);
            else    y=A[ind];
            ld alfa=v.sc*(v.fi-y.fi)/(x.fi-y.fi);
            ld beta=v.sc*(x.fi-v.fi)/(x.fi-y.fi);
            if(alfa<=x.sc+eps&&beta<=y.sc+eps)
            {
                x.sc-=alfa;
                y.sc-=beta;
                if(x.sc>eps)    Q.push(x);
                if(y.sc>eps)
                {
                    if(ind<(int)A.size())   A[ind]=y;
                }
                else            ind++;
                break;
            }
            else    if(x.sc*(v.fi-x.fi)/(y.fi-v.fi)<=y.sc+eps)
            {
                y.sc-=x.sc*(v.fi-x.fi)/(y.fi-v.fi);
                v.sc-=x.sc*(y.fi-x.fi)/(y.fi-v.fi);
                if(y.sc>eps)
                {
                    if(ind<(int)A.size())   A[ind]=y;
                }
                else            ind++;
            }
            else
            {
                x.sc-=y.sc*(v.fi-y.fi)/(x.fi-v.fi);
                v.sc-=y.sc*(x.fi-y.fi)/(x.fi-v.fi);
                if(x.sc>eps)    Q.push(x);
                ind++;
            }
        }
    }
    return cout<<"TAK\n",0;
}

int main()
{
    ios_base::sync_with_stdio(0);
    int Z;
    cin>>Z;
    while(Z--)  solve();
    return 0;
}