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

using namespace std;

#define PB push_back
#define SZ(x) int((x).size())
#define REP(i, n) for(int i=0,_=(n);i<_;++i)
#define FOR(i, a, b) for(int i=(a),_=(b);i<=_;++i)
#define FORD(i, a, b) for(int i=(a),_=(b);i>=_;--i)

#ifdef DEBUG
#define DEB(x) (cerr << x)
#else
#define DEB(x)
#endif

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int INF = 1e9 + 9;

struct Tea {
    ll volume;
    ll temperature;

    bool operator<(const Tea &tea) const {
        return temperature < tea.temperature;
    }
};

void inline one() {
    int n;
    cin >> n;
    vector <Tea> actual_list, expected_list;


    ll total_energy_actual = 0;
    ll total_energy_expected = 0;

    ll min_temperature_actual = INF;
    ll min_temperature_expected = INF;

    ll max_temperature_actual = -1;
    ll max_temperature_expected = -1;

    REP (i, n) {
        ll volume, temperature_actual, temperature_expected;
        cin >> volume >> temperature_actual >> temperature_expected;

        Tea actual_tea = {
                volume,
                temperature_actual,
        };
        actual_list.PB(actual_tea);

        Tea expected_tea = {
                volume,
                temperature_expected,
        };
        expected_list.PB(expected_tea);

        total_energy_actual += volume * temperature_actual;
        total_energy_expected += volume * temperature_expected;

        min_temperature_actual = min(min_temperature_actual, temperature_actual);
        min_temperature_expected = min(min_temperature_expected, temperature_expected);

        max_temperature_actual = max(max_temperature_actual, temperature_actual);
        max_temperature_expected = max(max_temperature_expected, temperature_expected);
    }
    bool ok = (total_energy_actual == total_energy_expected) && (min_temperature_actual <= min_temperature_expected) &&
              (max_temperature_actual >= max_temperature_expected);
    DEB(total_energy_actual << " == " << total_energy_expected
                            << "  mins: " << min_temperature_actual << " <= " << min_temperature_expected
                            << "  maxs: " << max_temperature_actual << " >= " << max_temperature_expected
                            << "\n");

    if (ok) {
        sort(actual_list.begin(), actual_list.end());
        sort(expected_list.begin(), expected_list.end());
        vector <ll> final_energies(n), final_volumes(n);
        ll energy_deficit = 0;
        int a = 0, e = 0;
        while (a < n && e < n) {
            if (actual_list[a].volume == 0) {
                ++a;
                continue;
            }
            ll missing_volume = expected_list[e].volume - final_volumes[e];
            if (missing_volume == 0) {
                final_energies[e] -= energy_deficit;
                energy_deficit = 0;
                ll energy_expected = expected_list[e].volume * expected_list[e].temperature;
                if (final_energies[e] > energy_expected) {
                    ok = false;
                    break;
                }
                energy_deficit = energy_expected - final_energies[e];
                ++e;
                continue;
            }
            ll transferred_volume = min(actual_list[a].volume, missing_volume);
            actual_list[a].volume -= transferred_volume;
            final_volumes[e] += transferred_volume;
            final_energies[e] += transferred_volume * actual_list[a].temperature;
        }
    }

    cout << (ok ? "TAK" : "NIE") << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int z;
    cin >> z;
    while (z--)
        one();
}