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

const int M = 1000;
const long long Q = ((long long)(1e18)) + 1;

const int N = 250100;
const int INV = 8;

long long dp[M][M];
long long dp2[N][INV];

void init() {
	dp[0][0] = dp[1][0] = 1;
	for (int n = 2; n < M; n++) {
		for (int inv = 0; inv < M && inv <= n*(n-1)/2; inv++) {
			for(int x = 1; x <= n && x-1 <= inv; x++) {
				dp[n][inv] += dp[n-1][inv - x + 1];
				if(dp[n][inv] >= Q) {
					dp[n][inv] = Q; break;
				}
			}
//			if(dp[n][inv] < Q )printf("%lld ", dp[n][inv]);
		}
	//	printf("\n");
	}
	for(int inv = 0; inv < INV; inv++) dp2[M-1][inv] = dp[M-1][inv];
	for(int n = M; n < N; n++) {
		dp2[n][0] = 1;
		for(int inv = 1; inv < INV; inv++) {
			dp2[n][inv] = std::min(Q, dp2[n][inv-1] + dp2[n-1][inv]);
//			if(dp2[n][inv] < Q)printf("%lld ", dp2[n][inv]);
		}
	//	printf("\n");
	}
}

long long ub(int n) {
	return ((long long)n) * (n-1) / 2;
}

long long get(int n, long long inv) {
	long long w = ub(n);
	if (inv > w || inv < 0) 
		return 0;
	if (inv > w-inv) 
		inv = w-inv;
  if (inv == 0) return 1;	
	if (n < M) {
		if (inv < M)
			return dp[n][inv];
		else
			return Q;
	}
	if (inv < INV)
		return dp2[n][inv];
	return Q;
}

const int U = 1<<18;
int e[U+U];

void zb_init(int n) {
	for(int i = 1; i <= n; i++) e[U+i] = 1;
	for(int i = U-1; i > 0; i--)
		e[i] = e[i+i] + e[i+i+1];
}

int zb_find(int x) {
	int i;
	for (i = 1; i < U; ) {
		e[i]--;
		if (e[i+i] >= x) i=i+i;
		else {
			x -= e[i+i];
			i = i+i+1;
		}
	}
	e[i]--;
	return i - U;
}

std::vector<int> go(int n, long long k) {
	long long inv = ub(n);
	if (inv % 2) return std::vector<int>();
	inv /= 2;
	if (get(n, inv) < k) return std::vector<int>();
	std::vector<int> ret;
	zb_init(n);
	for (int i = 0; i < n; i++) {
		long long r = ub(n-i-1);
		for (long long x = std::max(inv - r, 0LL) + 1; x <= n-i; x++) {
			long long q = get(n-i-1, inv - x + 1);
			//printf("(%lld %lld -- %d %d %lld) ",q, k, n-i, x, inv);
			if (q >= k) {
		//		printf("%d ", x);
				ret.push_back(zb_find(x));
				inv -= x-1;
				break;
			} else {
				k -= q;
			}
		}
	}
//	printf("\n");
	return ret;
}

int main() {
	init();
	int n;
	long long k;
	scanf("%d %lld",&n,&k);
	std::vector<int> x = go(n, k);
	if (x.empty()) {
		printf("NIE\n");
	} else {
		printf("TAK\n");
		for(int i = 0; i < n; i++) printf("%d ", x[i]);
		printf("\n");
	}
	return 0;
}