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
125
126
127
128
129
130
131
132
#include <algorithm>
#include <cstdio>
#include <initializer_list>
#include <vector>
using namespace std;

unsigned constexpr M = 101;
unsigned constexpr LOG = 20;
unsigned constexpr BASE = 1 << LOG;

unsigned m;

struct Query {
    unsigned a, b, c;
    Query(unsigned const _a, unsigned const _b, unsigned const _c): a(_a), b(_b), c(_c) {}
};

class Node {
	Node *l = nullptr, *r = nullptr;
public:
	Node * left() {
		if(l == nullptr) l = new Node(range/2);
		return l;
	}
	Node * right() {
		if(r == nullptr) r = new Node(range/2);
		return r;
	}

	Node(unsigned const _range): non_zero_count(_range), value_count{}, to_push{}, range(_range) {
		value_count[m] = range;
	}

    void push() {
    	for(auto const & v : {left(), right()}) {
			for(unsigned i = 1 ; i <= m ; ++i) {
				unsigned const diff = min(v->value_count[i], to_push[i]);
				v->value_count[i] -= diff;
				v->value_count[i-1] -= diff;
				v->to_push[i] += diff;
				to_push[i] -= diff;
			}
			v->updateInternalValues();
    	}
    }

    void update() {
    	for(unsigned i = 1 ; i <= m ; ++i)
			value_count[i] = left()->value_count[i] + right()->value_count[i];
		non_zero_count = left()->non_zero_count + right()->non_zero_count;
    }

    void updateInternalValues() {
    	non_zero_count -= value_count[0];
		value_count[0] = 0;
    }

    void subValue(unsigned & c) {
		for(unsigned i = 1 ; c != 0 && i <= m ; ++i) {
			unsigned const diff = min(value_count[i], c);
			value_count[i] -= diff;
			value_count[i-1] += diff;
			to_push[i] += diff;
			c -= diff;
		}
		updateInternalValues();
    }

    static void performQuery(unsigned const a, unsigned const b, unsigned & c, unsigned const p = 1, unsigned const k = BASE, Node * const v = root) {
//    	printf("performQuery( a: %u, b: %u, c: %u, p: %u, k: %u, v->non_zero_count: %u )\n", a, b, c, p, k, v->non_zero_count);
    	if(c == 0)
			return;

		if(a == p && b == k)
            return v->subValue(c);

		v->push();

		unsigned const avg = (p+k)/2;

        if(avg >= b)
			performQuery(a, b, c, p    , avg, v->left() );
		else if(avg < a)
			performQuery(a, b, c, avg+1, k  , v->right());
		else {
			performQuery(a    , avg, c, p    , avg, v->left() );
			performQuery(avg+1, b  , c, avg+1, k  , v->right());
		}

		v->update();
    }

    unsigned non_zero_count;
    unsigned value_count[M];
	unsigned to_push[M];
	unsigned const range;

private:
	static Node * const root;
};
Node * const Node::root = new Node(BASE);

struct Cmp {
    bool operator () (Query const & a, Query const & b) const {
		if(a.b != b.b)
			return a.b < b.b;
		return a.a > b.a;
    }
};

vector<Query> queries;

int main() {
	unsigned n;
	scanf("%u%u", &n, &m);
	queries.reserve(n);
	unsigned n_copy = n;
	while(n_copy--) {
		unsigned a, b, c;
		scanf("%u%u%u", &a, &b, &c);
		queries.emplace_back(a, b, c);
	}
	sort(queries.begin(), queries.end(), Cmp());
	for(auto & q : queries) {
		Node::performQuery(q.a+1, q.b, q.c);
		if(q.c != 0) {
			printf("NIE");
			return 0;
		}
	}
	printf("TAK");
}