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

long double e = (long double)1e-9;

int main(){
    int t;
    scanf("%d", &t);
    while (t--){
        int n;
        scanf("%d", &n);
        std::vector<std::pair<long long, long double>> a, b;
        long long e1 = 0, e2 = 0;
        for (int i = 0; i < n; i++){
            long long _l, _a, _b;
            scanf("%lld%lld%lld", &_l, &_a, &_b);
            a.push_back(make_pair(_a, (long double)_l));
            b.push_back(make_pair(_b, (long double)_l));
            e1 += _l * _a;
            e2 += _l * _b;
        }
        if (e1 != e2){
            printf("NIE\n");
            continue;
        }
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        /*for (int i = 0; i < n; i++){
            printf("(%lld %lf) ", b[i].first, (double)b[i].second);
        }
        printf("\n");
        for (int i = 0; i < n; i++){
            printf("(%lld %lf) ", a[i].first, (double)a[i].second);
        }
        printf("\n");*/
        int p = 0, q = 0;
        bool ok = true;
        for (int i = 0; i < (int)b.size(); i++){
            //printf("cc %d %d %lld %lf %d %lld %lf\n", i, p, a[p].first, (double)a[p].second, i, b[i].first, (double)b[i].second);
            while ((q < (int)a.size()) && (a[q].first < b[i].first)){
                q++;
            }
            //printf("cd %d\n", q);
            while (q < (int)a.size()){
                if (a[q].first == b[i].first){
                    if (a[q].second >= b[i].second){
                        a[q].second -= b[i].second;
                        b[i].second = 0;
                        break;
                    }
                    else {
                        b[i].second -= a[q].second;
                        a[q].second = 0;
                        q++;
                        continue;
                    }
                }
                else if ((a[p].first >= b[i].first) && (b[i].second > e)){
                    //printf("h1 %d %lld %lf %d %lld %lf\n", p, a[p].first, (double)a[p].second, i, b[i].first, (double)b[i].second);
                    ok = false;
                    break;
                }
                else {
                    long double ratio = (long double)(b[i].first - a[p].first) / (a[q].first - a[p].first);
                    if ((a[p].second <= b[i].second * (1 - ratio)) && (a[p].second * ratio <= a[q].second * (1 - ratio))){
                        b[i].second -= a[p].second / (1 - ratio);
                        a[q].second -= a[p].second * ratio / (1 - ratio);
                        a[p].second = 0;
                    }
                    else if ((a[q].second <= b[i].second * ratio) && (a[q].second * (1 - ratio) <= a[p].second * ratio)){
                        b[i].second -= a[q].second / ratio;
                        a[p].second -= a[q].second * (1 - ratio) / ratio;
                        a[q].second = 0;
                    }
                    else {
                        a[p].second -= b[i].second * (1 - ratio);
                        a[q].second -= b[i].second * ratio;
                        b[i].second = 0;
                    }
                    if (a[p].second < e){
                        p++;
                    }
                    if (a[q].second < e){
                        //printf("wro %d %d %d %lf %lld %lld %lld %lf %lf %lf\n", q, p, i, (double)ratio, a[p].first, b[i].first, a[q].first, (double)a[p].second, (double)b[i].second, (double)a[q].second);
                        q++;
                    }
                    if (b[i].second < e){
                        break;
                    }
                }
            }
            if ((!ok) || ((q >= (int)a.size()) && (!(b[i].second < e)))){
                //if (t == 100 - 57)
                //printf("h2 %d %d %d %d %d %.20lf\n", i, n, q, (int)a.size(), (int)ok, (double)b[i].second);
                ok = false;
                break;
            }
        }
        if (!ok){
            printf("NIE\n");
        }
        else {
            printf("TAK\n");
        }
    }
}