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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
#include<stack>

#define SC(n) scanf("%d", &n)
#define SC2(n, m) scanf("%d %d", &n, &m)
#define SCC(c) scanf(" %c", &c)
#define SCS(b) scanf("%s", b)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define FORE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define FORIT(i, c, typ) for(typ::iterator i = c.begin(); i != c.end(); ++i)
#define PR(n) printf("%d ", (int) (n)) 
#define PRN(n) printf("%d\n", (int) (n)) 
#define elif else if
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
#define all(v) v.begin(), v.end()
#define itr iterator
#define DBG if(0) printf

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef pair<pi, int> pii;
typedef vector<pii> vpii;
typedef vector<vpi> vvpi;
typedef map<int, vpi> mvpi;

const int NMAX = 1000*100 + 7, INF = 2000*1000*1000 + 7;

int n, zz, a, d, k1, k2;
pii p1[NMAX], p2[NMAX];
ll z;

int main() {
	SC2(n,zz);
	z = zz;
	
	REP(i,n) {
		SC2(d,a);
		if(a>d)
			p1[k1++] = mp(mp(d,a),i);
		else
			p2[k2++] = mp(mp(a,d),i);
	}
	sort(p1, p1 + k1);
	sort(p2, p2 + k2);
	
	FORD(i, k2-1, 0)
		p1[k1++] = mp(mp(p2[i].xx.yy, p2[i].xx.xx), p2[i].yy);
		
	REP(i, n)
		if(z <= p1[i].xx.xx) {
			printf("NIE");
			return 0;
		}
		else
			z += p1[i].xx.yy - p1[i].xx.xx;
	
			
	printf("TAK\n");
	REP(i, n)
		PR(p1[i].yy + 1);
	return 0;
}