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

int turn = 1000001;

struct Task {
    Task(int s, int f, int l) : start(s), finish(f), len(l) {}
    int start;
    int finish;
    int len;
};

bool cmp3(const Task& a, const Task& b) {
    return a.start < b.start;
}

bool cmp2(const Task& a, const Task& b) {
    return a.finish < b.finish;
}

int space_left(const Task& a) {
    return a.finish - turn - a.len;
}

bool cmp(const Task& a, const Task& b) {
    return space_left(a) < space_left(b);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Task> input;
    for (int i = 0; i < n; i++) {
        int s, f, l;
        cin >> s >> f >> l;
        turn = min(turn, s);
        input.push_back(Task(s, f, l));
    }
    sort(input.begin(), input.end(), cmp3);
    vector<Task> todo;
    vector<Task> current;

    int in = 0;
    bool ret = true;
    while (ret) {
        while (in < input.size() && turn == input[in].start) {
            current.push_back(input[in]);
            in++;
        }

        sort(current.begin(), current.end(), cmp2);
        int step = in < input.size() ? input[in].start - turn : 1000001;
        for (int i = 0; i < current.size(); i++) {
            step = min(step, current[i].len);
            if (space_left(current[i]) == 0) {
                todo.push_back(current[i]);
                current.erase(current.begin() + i);
                --i;
                continue;
            }
            if (space_left(current[i]) < 0) {
                ret = false;
            }
        }
        for (int i = 0; i < todo.size(); i++) {
            step = min(step, todo[i].len);
            if (space_left(todo[i]) < 0) {
                ret = false;
            }
        }
        for (int i = m - todo.size(); i < current.size(); i++) {
            step = min(step, space_left(current[i]));
        }

        int k = m;
        if (todo.size() > m) ret = false;
        for (int i = 0; i < todo.size(); i++) {
            todo[i].len -= step;
            k--;
        }
        for (int i = 0; i < todo.size(); i++) {
            if (todo[i].len == 0) {
                if (todo[i].finish < turn) ret = false;
                todo.erase(todo.begin() + i);
                i--;
            }
        }
        for (int i = 0; i < current.size() || k == 0; i++) {
            current[i].len -= step;
            k--;
        }
        for (int i = 0; i < current.size(); i++) {
            if (current[i].len == 0) {
                if (current[i].finish < turn) ret = false;
                current.erase(current.begin() + i);
                i--;
            }
        }
        turn += step;
        if (in == input.size() && todo.empty() && current.empty()) {
            break;
        }
    }


    if (ret) cout << "TAK" << endl;
    else cout << "NIE" << endl;





    return 0;
}