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

const int MAXT = 101;
const int MAXN = 1000001;

int n, m, mint = numeric_limits<int>::max(), maxt = 0;

int p[MAXT], q[MAXT], t[MAXT];
vector<int> act;
priority_queue<pair<int,int>> pq, qq;
bool used[MAXN];


void vdel(int x) {
    for(int i = 0; i < act.size(); i++) {
        if(act[i] == x) {
            swap(act.back(), act[i]);
            act.pop_back();
            return;
        }
    }
}


int main() {
    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        cin >> p[i] >> q[i] >> t[i];
        mint = min(p[i], mint);
        maxt = max(q[i], maxt);
    }
//    cout << mint << ' ' << maxt << endl;
    for(int i = 0; i < n; i++) {
        pq.push(make_pair(-p[i], i));
        qq.push(make_pair(-q[i], i));
    }
     for(int i = mint; i < maxt; i++) {
        while(!pq.empty() && -pq.top().first == i) {
            act.push_back(pq.top().second);
            pq.pop();
        }
        while(!qq.empty() && -qq.top().first == i) {
            vdel(qq.top().second);    
            qq.pop();
        }
        if(act.size() == m) {
//            cout << "ZMNIEJSZAMY W " << i << endl;
            used[i] = 1;
            for(int j = 0; j < m; j++) {
                t[act[j]]--;
            }
        }

    }
    act.clear();
    for(int i = 0; i < n; i++) {    
        pq.push(make_pair(-p[i], i));
        qq.push(make_pair(-q[i], i));
    }
 
    priority_queue<pair<int,int>> crt;
//    cout << "-> " << mint << ' ' << maxt << endl;
    for(int i = mint; i <= maxt; i++) {
//        cout << "----------\nRUNDA " << i << endl;
        while(!pq.empty() && -pq.top().first == i) {
//            cout << "WRZUCAM " << pq.top().second << '\n';
            act.push_back(pq.top().second);
            pq.pop();
        }
        while(!qq.empty() && -qq.top().first == i) {
            if(t[qq.top().second] > 0) {
                cout << "NIE\n";
                return 0;
            }
//            cout << "POCIEMU " << qq.top().second << endl;
            vdel(qq.top().second);
            qq.pop();
        }
        if(used[i])continue;
        for(auto x : act) {
            if(t[x] > 0) {
//                cout << "TASK " << x << " DYSTANS " << q[x]-i-t[x] << endl; 
                crt.push(make_pair(-(q[x] - i - t[x]), x));
            }
        }
        for(int j = 0; j < m; j++) {
            if(crt.empty())break;
            auto x = crt.top().second;
            crt.pop();
//            cout << "BIERE TASK " << x << endl;
            t[x]--;
        }
        while(!crt.empty())crt.pop();
    }
    cout << "TAK\n";


    return 0;
}