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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

//#define DEBUG

struct Mug {
	int vol;
	int temp;
};
int n,t,vol;
const int MAX_N = 100002;
Mug current[MAX_N], target[MAX_N];

bool solve() {
    cin>>n;
    for(int i=0;i<n;++i) {
				cin>>vol>>current[i].temp>>target[i].temp;
				current[i].vol=target[i].vol=vol;
    }
    sort(current, current+n, [](const Mug& m1, const Mug& m2) {
        return m1.temp<m2.temp;
    });
    sort(target, target+n, [](const Mug& m1, const Mug& m2) {
        return m1.temp<m2.temp;
    });
    Mug *targetMug = target, *currentMug = current;
    int totalQ, totalVol;
    int j=0;
    int stack = 0;
    for(int i=0;i<n;++i,++targetMug) {
				totalQ=totalVol=0;
				while(j<n && currentMug->vol+totalVol < targetMug->vol) {
#if defined(HOME) && defined(DEBUG)
					printf("using %4d x %4d --> +%8d\n", currentMug->vol, currentMug->temp, currentMug->vol*currentMug->temp);
#endif
					totalQ += currentMug->vol * currentMug->temp;
					totalVol += currentMug->vol;
					++j;
					++currentMug;
				}
				if(j==n)
					return false;
				totalQ += (targetMug->vol-totalVol) * currentMug->temp;
				currentMug->vol -= targetMug->vol-totalVol;
				stack += target[i].vol*target[i].temp - totalQ;
#if defined(HOME) && defined(DEBUG)
				printf("%4d %4d - need %8d, got %8d (diff %8d, stack %8d)\n", target[i].vol, target[i].temp, target[i].vol*target[i].temp, totalQ, target[i].vol*target[i].temp - totalQ, stack);
#endif
				if(stack<0)
					return false;
    }
    return stack == 0;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin>>t;
    for(int i=0;i<t;++i)
        cout<<(solve()?"TAK":"NIE")<<endl;
}