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
#include <iostream>
#include <math.h>
#include <map>
#include <vector>
#include <algorithm>

typedef long long int ll;

int P, N;
ll L, A, B;

void show(std::map<ll, ll> MINUS, std::map<ll, ll> PLUS) {
    std::cout << "MINUS: ";
    for (auto &it: MINUS) {
        std::cout << "(" << it.first << ", " << it.second << ") ";
    }
    std::cout << std::endl;

    std::cout << "PLUS: ";
    for (auto &it: PLUS) {
        std::cout << "(" << it.first << ", " << it.second << ") ";
    }
    std::cout << std::endl;
}

bool single() {
    std::cin >> N;

    std::map<ll, ll> T;
    ll energy = 0;

    for (int i = 0; i < N; i ++) {
        std::cin >> L >> A >> B;

        if (T.find(A) == T.end())
            T.insert(std::make_pair(A, 0));
        if (T.find(B) == T.end())
            T.insert(std::make_pair(B, 0));

        T.find(A) -> second += L;
        T.find(B) -> second -= L;

        energy += (A - B) * L;
    }

    if (energy != 0) return false;

    std::map<ll, ll> PLUS;
    std::map<ll, ll> MINUS;

    for (auto &it: T) {
        if (it.second > 0)
            PLUS.insert(std::make_pair(it.first, it.second));
        else if (it.second < 0)
            MINUS.insert(std::make_pair(it.first, -it.second));
    }

    while (MINUS.begin() != MINUS.end()) {
        auto L_minus = MINUS.begin();

        auto L_plus = PLUS.begin();
        auto R_plus = PLUS.upper_bound(L_minus -> first);

        if (L_plus -> first > L_minus -> first) // no left PLUS
            return false;
        if (R_plus == PLUS.end())               // no right PLUS
            return false;

        auto R_minus = std::prev(MINUS.upper_bound(R_plus -> first)); // may be same as L_minus, check this later

        // should be L_PLUS > L_MINUS > R_MINUS > R_PLUS

        auto L_minus_key = L_minus -> first, R_minus_key = R_minus -> first;
        auto L_plus_key = L_plus -> first, R_plus_key = R_plus -> first;

        auto L_dist = L_minus_key - L_plus_key, R_dist = R_plus_key - R_minus_key;
        auto L_tea = L_plus -> second, R_tea = R_plus -> second;

        ll L_dist_mul = 1, R_dist_mul = 1;    // multipliers to combat energy distribution
        ll L_tea_mul = 1, R_tea_mul = 1;

        auto dist = std::min(L_dist, R_dist);
        auto tea = std::min(L_tea, R_tea);

        if (L_tea > tea && R_dist > dist)
            L_tea_mul = R_dist_mul = std::min(L_tea / tea, R_dist / dist);
        if (L_dist > dist && R_tea > tea)
            L_dist_mul = R_tea_mul = std::min(L_dist / dist, R_tea / tea);

        if (PLUS.find(L_plus_key + (dist * L_dist_mul)) == PLUS.end()) // add flow if none exist
            PLUS.insert(std::make_pair(L_plus_key + (dist * L_dist_mul), 0));
        if (PLUS.find(R_plus_key - (dist * R_dist_mul)) == PLUS.end())
            PLUS.insert(std::make_pair(R_plus_key - (dist * R_dist_mul), 0));

        PLUS.find(L_plus_key) -> second -= tea * L_tea_mul;     // move tea
        PLUS.find(R_plus_key) -> second -= tea * R_tea_mul;

        PLUS.find(L_plus_key + (dist * L_dist_mul)) -> second += tea * L_tea_mul;
        PLUS.find(R_plus_key - (dist * R_dist_mul)) -> second += tea * R_tea_mul;

        //cleanup
        if (PLUS.find(L_plus_key) -> second == 0)
            PLUS.erase(L_plus_key);
        if (PLUS.find(R_plus_key) -> second == 0)
            PLUS.erase(R_plus_key);

        auto p = PLUS.find(L_plus_key + (dist * L_dist_mul));
        auto m = MINUS.find(L_plus_key + (dist * L_dist_mul));

        if (p != PLUS.end() && m != MINUS.end()) {
            if (p -> second > m -> second) {
                p -> second -= m -> second;
                MINUS.erase(m -> first);
            } else if (p -> second < m -> second) {
                m -> second -= p -> second;
                PLUS.erase(p -> first);
            } else {
                PLUS.erase(p -> first);
                MINUS.erase(m -> first);
            }
        }

        p = PLUS.find(R_plus_key - (dist * R_dist_mul));
        m = MINUS.find(R_plus_key - (dist * R_dist_mul));

        if (p != PLUS.end() && m != MINUS.end()) {
            if (p -> second > m -> second) {
                p -> second -= m -> second;
                MINUS.erase(m -> first);
            } else if (p -> second < m -> second) {
                m -> second -= p -> second;
                PLUS.erase(p -> first);
            } else {
                PLUS.erase(p -> first);
                MINUS.erase(m -> first);
            }
        }
    }

    return true;
}


int main() {
    std::ios::sync_with_stdio(false);

    std::cin >> P;

    for (int i = 0; i < P; i++) {
        if (single())
            std::cout << "TAK\n";
        else
            std::cout << "NIE\n";
    }
}