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
#include <algorithm>
#include <cassert>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

namespace {

using ll = long long;

bool solve(vector<tuple<int, int, int>> const& data)
{
  vector<pair<int, int>> src;
  vector<pair<int, int>> dst;
  for (auto const& [l, a, b]: data) {
    src.emplace_back(a, l);
    dst.emplace_back(b, l);
  }
  sort(src.begin(), src.end());
  sort(dst.begin(), dst.end());
  ll e = 0;
  auto i = src.begin();
  auto j = dst.begin();
  while (i != src.end() && j != dst.end()) {
    auto a = i->first;
    auto b = j->first;
    auto l = min(i->second, j->second);
    e += ll{b - a} * l;
    if (e < 0) return false;
    i->second -= l;
    if (i->second == 0) ++i;
    j->second -= l;
    if (j->second == 0) ++j;
  }
  return e == 0;
}

}

int main()
{
  iostream::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;
  while (t > 0) {
    --t;
    int n;
    cin >> n;
    vector<tuple<int, int, int>> data(n);
    for (auto& [l, a, b]: data) {
      cin >> l >> a >> b;
    }
    cout << (solve(data) ? "TAK\n": "NIE\n");
  }

  return 0;
}