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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
#define mp make_pair
#define f first
#define s second
using namespace std;
int zapy,n;
long long a[100005],b[100005],c[100005],wyn1,wyn2,nie,aspel,bspel,an,bn,suma,litry;
map<long long, long long>zlicz;
priority_queue<long long>qmax,qmin;
priority_queue<pair<long long, long long> >q,qn;
int main()
{
ios_base::sync_with_stdio(0);
cin>>zapy;
while(zapy--)
    {
    cin>>n;
    while(!q.empty())q.pop();
    while(!qn.empty())qn.pop();
    for(int i=1;i<=n;i++)
        {
        cin>>a[i]>>b[i]>>c[i];
        q.push(mp(-c[i],a[i]));
        qn.push(mp(-b[i],a[i]));
        }
    suma=0;
    litry=0;
    while(!qn.empty())
        {
        bn=-qn.top().f;
        an=qn.top().s;
        qn.pop();
        while(!q.empty())
            {
            bspel=-q.top().f;
            aspel=q.top().s;
            if(litry>=aspel)
                {
                if(suma<=bspel*litry&&(suma+an*bn)>=bspel*(litry+an))
                    {
                    suma-=aspel*bspel;
                    litry-=aspel;
                    q.pop();
                    }
                else break;
                }
            else if(aspel-litry<=an)
                {
                if((suma+(aspel-litry)*bn)<=bspel*aspel&&(suma+an*bn)>=bspel*(litry+an))
                    {
                    suma-=aspel*bspel;
                    litry-=aspel;
                    q.pop();
                    }
                else break;
                }
            else break;
            }
        suma+=an*bn;
        litry+=an;
        }
    if(q.empty())cout<<"TAK"<<'\n';
    else cout<<"NIE"<<'\n';
    }


/*cin>>zapy;
while(zapy--)
    {
    zlicz.clear();
    while(!qmax.empty())qmax.pop();
    while(!qmin.empty())qmin.pop();
    wyn1=0;
    wyn2=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        {
        cin>>a>>b>>c;
        if(zlicz[b]==0){qmax.push(b);qmin.push(-b);}
        zlicz[b]+=a;
        if(zlicz[c]==0){qmax.push(c);qmin.push(-c);}
        zlicz[c]-=a;
        wyn1+=a*b;
        wyn2+=a*c;
        }
    cout<<wyn1<<' '<<wyn2;
    if(wyn1==wyn2)
        {
        nie=0;
        while(!qmax.empty())
            {
            if(zlicz[qmax.top()]==0)qmax.pop();
            else if(zlicz[qmax.top()]<0)
                {
                nie=1;
                break;
                }
            else break;
            }
        while(!qmin.empty())
            {
            if(zlicz[-qmin.top()]==0)qmin.pop();
            else if(zlicz[-qmin.top()]<0)
                {
                nie=1;
                break;
                }
            else break;
            }
        if(nie)cout<<"NIE"<<'\n';
        else cout<<"TAK"<<'\n';
        }
    else cout<<"NIE"<<'\n';
    }
*/
}