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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <stack>

using namespace std;

bool is_equal(long double a, long double b) {
    long double EPS = 1e-8;
    return (abs(a - b) < EPS);
}

bool cmp(tuple<long double, long double, bool> a, tuple<long double, long double, bool> b) {
    if(!is_equal(get<1>(a), get<1>(b))) {
        return get<1>(a) < get<1>(b);
    }
    return get<2>(a);
}

int main() {
    ios_base::sync_with_stdio(false);
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        unsigned int n;
        long long int l, a, b;
        int ind;
        long double x, y;
        ind = 0;
        cin >> n;
        vector<tuple<long double, long double, bool> > v;
        vector<tuple<long double, long double> >v1;
        stack<tuple<long double, long double>> s1, s2;
        for (int i2 = 0; i2 < n; i2++) {
            cin >> l >> a >> b;
            v.emplace_back(l, a, true);
            v.emplace_back(l, b, false);
        }
        sort(v.begin(), v.end(), cmp);
        for(int i2 = (2 * n - 1); i2 >= 0; i2--){
            if(get<2>(v[i2])) {
                s2.push(make_tuple(get<0>(v[i2]), get<1>(v[i2])));
            }
        }
        for (int i2 = 0; i2 < 2 * n; i2++) {
            if(!get<2>(v[i2])){
                v1.emplace_back(get<0>(v[i2]), get<1>(v[i2]));
            }
        }
        while(!s2.empty() && get<1>(v1[ind]) > get<1>(s2.top())){
            s1.push(s2.top());
            s2.pop();
        }


        while (ind < n) {
            if (is_equal(get<0>(v1[ind]), 0.0)) {
                ind++;
                while(!s2.empty() && get<1>(v1[ind]) > get<1>(s2.top())){
                    s1.push(s2.top());
                    s2.pop();
                }
                continue;
            }
            if (!s1.empty() && is_equal(get<0>(s1.top()), 0.0)) {
                s1.pop();
                continue;
            }

            if (!s2.empty() && is_equal(get<0>(s2.top()), 0.0)) {
                s2.pop();
                continue;
            }

            while(!s2.empty() && get<1>(v1[ind]) > get<1>(s2.top())){
                s1.push(s2.top());
                s2.pop();
            }

            if(s1.empty() && s2.empty()){
                break;
            }
            if(!s1.empty() && !s2.empty()) {
                x = (get<0>(v1[ind]) * (get<1>(v1[ind]) - get<1>(s2.top()))) / (get<1>(s1.top()) - get<1>(s2.top()));
                if (is_equal(x, 0.0)) {
                    x = 0.0;
                }
                y = (get<0>(v1[ind]) * (get<1>(s1.top()) - get<1>(v1[ind]))) / (get<1>(s1.top()) - get<1>(s2.top()));
                if (is_equal(y, 0.0)) {
                    y = 0.0;
                }
                if (x <= get<0>(s1.top()) && (y <= get<0>(s2.top()))) {
                    get<0>(v1[ind]) = 0.0;
                    get<0>(s1.top()) = get<0>(s1.top()) - x;
                    get<0>(s2.top()) = get<0>(s2.top()) - y;
                    continue;
                }
                if ((x >= get<0>(s1.top()))) {
                    get<1>(v1[ind]) =
                            (((get<0>(v1[ind])) * (get<1>(v1[ind]))) - ((get<0>(s1.top())) * (get<1>(s1.top())))) /
                            ((get<0>(v1[ind])) - (get<0>(s1.top())));
                    get<0>(v1[ind]) = get<0>(v1[ind]) - get<0>(s1.top());
                    get<0>(s1.top()) = 0.0;
                    continue;
                }
                if ((y >= get<0>(s2.top()))) {
                    get<1>(v1[ind]) =
                            (((get<0>(v1[ind])) * (get<1>(v1[ind]))) - ((get<0>(s2.top())) * (get<1>(s2.top())))) /
                            ((get<0>(v1[ind])) - (get<0>(s2.top())));
                    get<0>(v1[ind]) = get<0>(v1[ind]) - get<0>(s2.top());
                    get<0>(s2.top()) = 0.0;
                    continue;
                }
            }
            if(s1.empty()){
                if(is_equal(get<1>(s2.top()), get<1>(v1[ind]))){
                    if(is_equal(get<0>(s2.top()), get<0>(v1[ind]))){
                        get<0>(s2.top()) = 0.0;
                        get<0>(v1[ind]) = 0.0;
                        continue;
                    }
                    if(get<0>(s2.top()) > get<0>(v1[ind])){
                        get<0>(s2.top()) = get<0>(s2.top()) - get<0>(v1[ind]);
                        get<0>(v1[ind]) = 0.0;
                        continue;
                    }
                    if(get<0>(s2.top()) < get<0>(v1[ind])){
                        get<0>(s2.top()) = 0.0;
                        get<0>(v1[ind]) = get<0>(v1[ind]) - get<0>(s2.top());
                        continue;
                    }
                }
                else{
                    break;
                }
            }
            if(s2.empty()){
                if(is_equal(get<1>(s1.top()), get<1>(v1[ind]))){
                    if(is_equal(get<0>(s1.top()), get<0>(v1[ind]))){
                        get<0>(s1.top()) = 0.0;
                        get<0>(v1[ind]) = 0.0;
                        continue;
                    }
                    if(get<0>(s1.top()) > get<0>(v1[ind])){
                        get<0>(s1.top()) = get<0>(s1.top()) - get<0>(v1[ind]);
                        get<0>(v1[ind]) = 0.0;
                        continue;
                    }
                    if(get<0>(s1.top()) < get<0>(v1[ind])){
                        get<0>(s1.top()) = 0.0;
                        get<0>(v1[ind]) = get<0>(v1[ind]) - get<0>(s1.top());
                        continue;
                    }
                }
                else{
                    break;
                }
            }

        }

        if (ind == n) {
            cout << "TAK\n";
        } else {
            cout << "NIE\n";
        }
        v.clear();
        v1.clear();
        while(!s1.empty()){
            s1.pop();
        }
        while(!s2.empty()){
            s2.pop();
        }
        /* for (auto &i2 : v) {
             cout << get<0>(i2) << " " << get<1>(i2) << " " << ((int)get<2>(i2)) << "\n";
         }
         cout << "\n\n\n";*/
    }
    return 0;
}