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

using namespace std;

typedef long long LL;
typedef pair<int, long double> PII;
const int N = 2e3+5;
long double EPS = 0.0000001;


void solve() {
    int n, l, a, b;
    LL sumSrc = 0, sumDest = 0;
    cin >> n;
    vector<PII> src(n);
    vector<PII> dest(n);
    queue<PII> Q;

    for(int i = 0;i < n;++i) {
        cin >> l >> a >> b;
        src[i] = {a, l};
        dest[i] = {b, l};
        sumSrc += 1LL*l*a;
        sumDest += 1LL*l*b;
    }
    if(sumSrc != sumDest) {
        cout << "NIE\n";
        return;
    }

    sort(src.begin(), src.end());
    sort(dest.begin(), dest.end());

    if(src[0].first > dest[0].first || src.back().first < dest.back().first) {
        cout << "NIE\n";
        return;
    }

    int destCt = 0;
    a = 0, b = 0;
    while(b < n && destCt < n) {
        if(src[b].second <= EPS) {
            ++b;
            continue;
        }
        if(dest[destCt].first == src[b].first) {
            if(src[b].second < dest[destCt].second) {
                dest[destCt].second -= src[b].second;
                src[b].second = 0.0;
                ++b;
                continue;
            }
            src[b].second -= dest[destCt].second;
            ++destCt;
            continue;
        }
        if(dest[destCt].first+EPS >=src[b].first) {
            Q.push(src[b]);
            ++b;
            continue;
        }
        if(Q.empty()) {
            cout << "NIE\n";
            return;
        }
        PII past = Q.front();
        Q.pop();
        long double x = (dest[destCt].second * (dest[destCt].first-src[b].first)) / (past.first - src[b].first);
        long double y = (dest[destCt].second * (past.first-dest[destCt].first)) / (past.first - src[b].first);
        if(past.second+EPS >= x && src[b].second+EPS >= y) {
            past.second -= x;
            src[b].second -= y;
            ++destCt;
            if(past.second > EPS)
                Q.push(past);
            //cout << "1 case" << endl;
            continue;
        }
        else if((past.second*(dest[destCt].first-past.first)) / (src[b].first-dest[destCt].first) <= src[b].second+EPS) {
            src[b].second -= (past.second*(dest[destCt].first-past.first)) / (src[b].first-dest[destCt].first);
            dest[destCt].second -= (past.second*(src[b].first-past.first)) / (src[b].first-dest[destCt].first);
            //cout << "2 case" << endl;
            continue;

            //cout << "AAAA " << x << " " << y << " " << src[a+2].second << " " << (x*(dest[destCt].first-src[a+1].first)) / (src[b].first-dest[destCt].first) << endl;
        }
        else {
            past.second -= (src[b].second*(dest[destCt].first-src[b].first)) / (past.first-dest[destCt].first);
            dest[destCt].second -= (src[b].second*(past.first-src[b].first)) / (past.first-dest[destCt].first);
            if(past.second > EPS)
                Q.push(past);
            ++b;
            //cout << "3 case" << endl;
            continue;
        }
    }
    //cout << a << "  " << b <<" " << destCt << endl;
    if(destCt < n && dest[destCt].second > EPS) {
        cout << "NIE\n";
        return;
    }
    cout << "TAK\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;

    while(T --> 0)
        solve();

    return 0;
}