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
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define mp make_pair

priority_queue <pair<ll,ll>, vector< pair<ll,ll> >, greater< pair<ll,ll> > > prl, prl1;

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        long long a,b,c, sum=0,ile=0;
        scanf("%d", &n);
        for(int i=0; i<n; ++i)
        {
            scanf("%lld%lld%lld", &a, &b, &c);
            prl.push(mp(b,a));
            prl1.push(mp(c,a));
        }
        while(!prl.empty())
        {
            pair<ll,ll> f = prl.top();
            prl.pop();
            sum += f.first*f.second;
            ile += f.second;
            while(!prl1.empty())
            {
                pair<ll,ll> g = prl1.top();
                if (ile >= g.second && sum >= ile * g.first)
                {
                    ile-=g.second;
                    sum-=g.first*g.second;
                    prl1.pop();
                }
                else
                    break;
			}
			if(!prl1.empty())
			{
				pair<ll,ll> g = prl1.top();
				if (ile!=0 && ile<g.second && sum >= ile * g.first)
					break;
				if (ile == 0 && sum!=0)
					break;
			}
        }
        if (prl1.empty()&&sum==0&&ile==0)
            puts("TAK");
        else
            puts("NIE");
        while(!prl.empty())
			prl.pop();
        while(!prl1.empty())
            prl1.pop();
    }
    return 0;
}