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
#include <cstdio>
#include <tuple>
#include <vector>
#include <algorithm>
#include <set>
#include <functional>

void empty(int n_args, ...) {
}

// #define _DEBUG 1;

#ifdef _DEBUG
#define dprintf printf
#else
#define dprintf empty;
#endif

struct Task {
	int p, k, c;
	Task(int pp, int kk, int cc): p(pp), k(kk), c(cc) {}
};

struct cmp {
    bool operator() (const Task& a, const Task& b) const{
        if(a.p != b.p) {
        	return a.p < b.p;
        }
        return a.c < b.c;
    }
};

struct SuperMap {
	std::set<Task, cmp> pool;

	void init(int procs, int minp, int maxk) {
		for(int i = 0; i < procs; ++i) {
			pool.insert(Task(minp, maxk, i));
		}
	}

	void print_pool() {
		for(auto it = pool.begin(); it != pool.end(); ++it) {
			dprintf("%d-%d proc %d, ", it->p, it->k, it->c);
		}
		dprintf("\n");
	}

	bool reserve(Task& task) {
		print_pool();
		dprintf("reserve task %d %d %d\n", task.p, task.k, task.c);
		int time_left = task.c, pos = task.p;
		while(time_left > 0) {
			dprintf("tl=%d pos=%d\n", time_left, pos);
			auto it = pool.lower_bound(Task(pos, 0, -1));
			Task range = *it;
			if(it == pool.end()) {
				dprintf("end of pools :(\n");
				return false;
			}
			if(time_left > range.k - pos) {
				dprintf("not enough, take from %d to %d\n", pos, range.k);
				time_left -= range.k - pos;
				pos = range.k;
				pool.erase(it);
				if(range.p < pos) {
					pool.insert(Task(range.p, pos, range.c));
				}
			}
			else {
				dprintf("enough, split? on %d\n", range.p + time_left);
				pool.erase(it);
				if(range.p < pos) {
					pool.insert(Task(range.p, pos, range.c));
				}
				if(range.p + time_left < range.k) {
					pool.insert(Task(range.p + time_left, range.k, range.c));
				}
				time_left = 0;
			}
		}
		dprintf("\n");
		return true;
	}
};

void solve() {
	int n, m;
	int p, k, c;
	int minp=1000000, maxk=0;
	std::vector<Task> tasks;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; ++i) {
		scanf("%d %d %d", &p, &k, &c);
		minp = std::min(minp, p);
		maxk = std::max(maxk, k);
		tasks.push_back(Task(p, k, c));
	}
	// dprintf("minp %d maxk %d\n", minp, maxk);
	SuperMap sm;
	sm.init(m, minp, maxk);	
	std::sort(tasks.begin(), tasks.end(), [](const Task &a, const Task &b) { return a.k < b.k; });
	// for(auto i = tasks.begin(); i != tasks.end(); ++i) 
	// 	dprintf("%d %d %d\n", i->p, i->k, i->c);

	for(auto i = tasks.begin(); i != tasks.end(); ++i) {
		Task task = *i;
		if(!sm.reserve(task)) {
			printf("NIE\n");
			return;
		}	
	}
	sm.print_pool();
	printf("TAK\n");
}

int main() {
	solve();
	return 0;
}