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

using namespace std;

template<typename elem_t>
istream& operator>>(istream &is, vector<elem_t> &t) {
  for(typename vector<elem_t>::iterator it = t.begin(); it != t.end(); it++) is >> *it;
  return is;
}

template<typename elem_t>
ostream& operator<<(ostream &os, vector<elem_t> const &t) {
  if(t.empty()) return (os << "[]");
  typename vector<elem_t>::const_iterator it = t.begin();
  os << '[' << *it;
  while(++it != t.end()) {
    os << ", " << *it;
  }
  os << ']';
  return os;
}

struct Task {
  int i, t0, t1, c, d;
  
  Task(): i(-1), t0(-1), t1(-1), d(0) { }
  
  friend istream& operator>>(istream &is, Task &t) { return (is >> t.t0 >> t.t1 >> t.c); }
  friend ostream& operator<<(ostream &os, Task const &t) { return (os << "Task(t0=" << t.t0 << ",t1=" << t.t1 << ",c=" << t.c << ")"); }
  
  struct lessT0 {
    bool operator()(Task const &a, Task const &b) const { return a.t0 < b.t0; }
  };
  
  struct lessT1 {
    bool operator()(Task const &a, Task const &b) const {
      if(a.t1 != b.t1) return a.t1 < b.t1;
      return a.i < b.i;
    }
  };
};


int main() {
  ios_base::sync_with_stdio(false);
#ifndef LOCAL_TESTS
  cin.tie(NULL);
#endif
  
  int n, m;
  cin >> n >> m;
  
  vector<Task> T(n);
  for(int i = 0; i < n; i++) T[i].i = i;
  cin >> T;
  
  sort(T.begin(), T.end(), Task::lessT0());
  
  vector<int> D(n, 0);
  set<Task, Task::lessT1> S;
  
  for(int t = 0, i=0; i < n or not S.empty(); t++) {
    while(i < n and T[i].t0 <= t) {
      S.insert(T[i]);
      i++;
    }
    
    int j = 0;
    for(set<Task, Task::lessT1>::iterator it = S.begin(); it != S.end() and j < m; j++) {
      if(t >= it->t1) goto NO;
      D[it->i]++;
      if(D[it->i] == it->c) {
        S.erase(it++);
      } else {
        it++;
      }
    }
  }
  
  cout << "TAK\n";
  goto END;
  
NO:
  cout << "NIE\n";
  
END:
  return 0;
}