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
#include <list>
#include <algorithm>
#include <cstdio>

using namespace std;

struct Prz {
  int a,b;
  int t;
  bool operator<(Prz p) {
    if(a == p.a)
      return b < p.b;
    return a < p.a;
  }
};

inline bool cmp(Prz a, Prz b){
  if(a.a == b.a)
    return a.b < b.b;
  return a.a < b.a;
}

const int T = 1<<20;
int need[2*T];

int get(int x) {
  return need[x+T];
}

void fix(int x = 1, int sum = 0){
  sum += need[x];
  if(x>=T){
    need[x] = sum;
  } else {
    need[x] = 0;
    fix(x*2, sum);
    fix(x*2+1, sum);
  }
}

void ins(int a, int b, int ba = 0, int bb = T-1, int r = 1) {
  if(a==ba and b==bb){
    need[r]++;
    return;
  }
  int m = (ba+bb)/2;
  if(b <= m) {
    ins(a, b, ba, m, r*2);
    return;
  }
  if(a > m){
    ins(a, b, m+1, bb, r*2+1);
    return;
  }
  ins(a, m, ba, m, r*2);
  ins(m+1, b, m+1, bb, r*2+1);
  return;
}

int los[T];

int n,m;
list<Prz> v;

int main() {
  scanf("%d%d", &n, &m);
  int fin = 0, beg = 4000000;
  for (int i = 0; i < n; ++i) {
    int a,b,k;
    scanf("%d%d%d", &a, &b, &k);
    Prz p;
    p.a = a;
    p.b = b;
    p.t = b - a - k;

    fin = max(p.b, fin);
    beg = min(p.a, beg);
    if(p.t > 0)
      v.push_back(p);
    ins(a,b-1);
  }
  fix();
  v.sort(cmp);

  for(int i = beg; i < fin; ++i) {
    los[i] = get(i) - m;
    if(los[i] < 0)
      los[i] = 0;
  }
  for(int i = beg; i < fin; ++i) {
    for(auto j = v.begin(); j != v.end();) {
      auto nextit = next(j);
      // printf("%d: %d-%d %d\n",i,j->a, j->b, j->t);
      if(j->b <= i){
        v.erase(j);
        j = nextit;
        continue;
      }
      if (j->a > i && los[i] > 0) {
        printf("NIE\n");
        return 0;
      }
      if(los[i] > 0) {
        if(j->t >= los[i]) {
          j->t -= los[i];
          los[i] = 0;
          break;
        } else {
          los[i] -= j->t;
          j->t = 0;
          v.erase(j);
        }
      }
      j = nextit;
    }
    if(los[i]!=0) {
      printf("NIE\n");
      return 0;
    }
  }

  printf("TAK\n");
  return 0;
}