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
#include <iostream>
#include <algorithm>
using namespace std;
pair<int,int> A[100000];
pair<int,int> B[100000];



int main() {
    int t,n,a,b,c;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i =0;i<n;i++){
            cin>>a>>b>>c;
            A[i].first = b;
            A[i].second = a;
            B[i].first = c;
            B[i].second = a;
        };
        sort(A,A+n);
        sort(B,B+n);
        //redukuj
        long long AS = 0,BS = 0;
        long long AL = 0,BL = 0;
        
        bool ok = true;
        AS = 0;
        BS = 0;
        for(int i =0;i<n;i++){
            AS += A[i].first*A[i].second;
            BS += B[i].first*B[i].second;
        }
        if(AS!=BS){
            ok = false;
        }
        AS = 0;
        BS = 0;
        int i = n-1;
        int j = n-1;
        while(true){
            if(A[i].first > B[j].first){
                AS += A[i].first*A[i].second;
                AL += A[i].second;
                i--;
            }
            else if(A[i].first == B[j].first){
              //  cout<<"R";
                AS += A[i].first*A[i].second;
                AL += A[i].second;
                BS += B[j].first*B[j].second;
                BL += B[j].second;
                i--;
                j--;
            }
            else if(A[i].first < B[j].first){
                BS += B[j].first*B[j].second;
                BL += B[j].second;
                j--;
            }
           // cout<<"AS "<<AS<< "("<<AL<<") BS "<<BS<< "("<<BL<<")\n";
            if(AS<BS){
                while(i>=0){
                    if(AL < BL){
                        if(AL+A[i].second <= BL){
                            AS += A[i].first*A[i].second;
                            AL += A[i].second;
                            i--;
                        }else{
                            long long h = BL-AL;
                            AS += A[i].first*(h);
                            AL += h;
                            A[i].second -=h;
                            break;
                        }
                    }else{
                        break;
                    }
                   // cout<<"AS "<<AS<< "("<<AL<<") BS "<<BS<< "("<<BL<<")\n";
                }
                //cout<<"AS "<<AS<< "("<<AL<<") BS "<<BS<< "("<<BL<<")\n";
                if(AS<BS){
                    ok = false;
                }
            }
          //  cout<<"AS "<<AS<< "("<<AL<<") BS "<<BS<< "("<<BL<<")\n";
            if(i<0 || j<0)break;
        }
      
        if(ok){
            cout<<"TAK\n";
        }else{
            cout<<"NIE\n";
        }
    }
    return 0;
}