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

using namespace std;

bool solve(vector<pair<int, int64_t>> &have, vector<pair<int, int64_t>> &want) {
    auto scalar_product = [](const auto &have) -> int64_t {
        int64_t sum_h = 0;
        for (const auto &[x, y] : have)
            sum_h += static_cast<int64_t>(x) * y;
        return sum_h;
    };
    if (scalar_product(have) != scalar_product(want)) return false;

    sort(have.begin(), have.end());
    sort(want.begin(), want.end());


    for (size_t i = 1; i < have.size(); ++i) {
        have[i].second += have[i - 1].second;
        want[i].second += want[i - 1].second;
    }

    using prevType = pair<int, int64_t>;
    prevType lastHave = have.back(), lastWant = want.back();

    vector<tuple<int64_t, bool, int> > zusammen;


    for (int i = static_cast<int>(have.size()) - 1; i >= 0; --i) {
        have[i].second = (i > 0 ? have[i - 1].second : 0);
        want[i].second = (i > 0 ? want[i - 1].second : 0);
        zusammen.emplace_back(have[i].second, true, have[i].first);
        zusammen.emplace_back(want[i].second, false, want[i].first);
    }

    sort(zusammen.begin(), zusammen.end());

    int64_t overArea = 0;

    for (int i = static_cast<int>(zusammen.size()) - 1; i >= 0; --i) {
        auto &[s, first, h] = zusammen[i];

        while (!have.empty() && have.back().second > s) have.pop_back();

        int currentHaveVal = (!have.empty() ? have.back().first : 0);

        if (first) {
            overArea += (lastHave.second - s) * h;
            lastHave = {h, s};
        } else {
            overArea -= (lastWant.second - s) * h;
            if (overArea + (currentHaveVal * (lastHave.second - s)) < 0)
                return false;
            lastWant = {h, s};
        }
    }

    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        vector<pair<int, int64_t>> have(n), want(n);
        for (int i = 0; i < n; ++i) {
            int l, a, b;
            cin >> l >> a >> b;
            have[i] = {a, l};
            want[i] = {b, l};
        }
        cout << (solve(have, want) ? "TAK" : "NIE") << '\n';
    }
}