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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

// per.cpp

typedef long long unsigned int llu;

static const llu TOO_MUCH = 1000000000000000000ULL; // 10^18

static const int TREE_BASE = 256 * 1024;
int tree[2 * TREE_BASE] = { 0 };

void init_tree(int n) {
	for (int i = TREE_BASE; i < TREE_BASE + n; i++) {
		tree[i] = 1;
	}
	for (int i = TREE_BASE - 1; i > 0; i--) {
		tree[i] = tree[2 * i] + tree[2 * i + 1];
	}
}

void remove_in_tree(int i) {
	i += TREE_BASE;
	tree[i] = 0;
	while (i > 1) {
		i /= 2;
		tree[i] = tree[2 * i] + tree[2 * i + 1];
	}
}

int nth_in_tree(int n) {
	int i = 1;
	while (i < TREE_BASE) {
		if (tree[2 * i] > n) {
			i *= 2;
		}
		else {
			n -= tree[2 * i];
			i = 2 * i + 1;
		}
	}
	assert(tree[i] == 1);
	return i - TREE_BASE;
}

static const int NUMS_ENTRIES = 63;
static const unsigned int nums[NUMS_ENTRIES][2] = {
	{ 1, 1 },
	{ 2, 2 }, { 3, 4 }, { 4, 7 }, { 5, 11 }, { 6, 16 }, { 7, 22 }, { 8, 29 }, { 9, 37 },
	{ 10, 46 }, { 11, 56 }, { 12, 67 }, { 13, 79 }, { 14, 92 }, { 15, 106 }, { 16, 121 },
	{ 17, 137 }, { 18, 154 }, { 19, 172 }, { 20, 191 }, { 21, 95 }, { 22, 71 }, { 23, 62 },
	{ 24, 55 }, { 25, 51 }, { 26, 47 }, { 27, 44 }, { 28, 42 }, { 29, 40 }, { 30, 38 },
	{ 31, 36 }, { 32, 35 }, { 33, 34 }, { 34, 32 }, { 35, 31 }, { 36, 30 }, { 38, 29 },
	{ 39, 28 }, { 40, 27 }, { 42, 26 }, { 44, 25 }, { 46, 24 }, { 48, 23 }, { 51, 22 },
	{ 55, 21 }, { 59, 20 }, { 63, 19 }, { 69, 18 }, { 76, 17 }, { 85, 16 }, { 97, 15 },
	{ 112, 14 }, { 133, 13 }, { 163, 12 }, { 209, 11 }, { 283, 10 }, { 412, 9 }, { 667, 8 },
	{ 1258, 7 }, { 2993, 6 }, { 10371, 5 }, { 69993, 4 }, { 1000000, 0 } // The last one is a dummy
};

llu first3k[3000][300] = { 0 };
llu others[250 * 1000][6] = { 0 };

inline llu get_raw(int n, int k) {
	if (n >= 3000) {
		return others[n - 3000][k];
	}
	else {
		return first3k[n][k];
	}
}

void make_tables(int upton) {
	first3k[1][0] = 1;
	for (int ns = 1; ns < NUMS_ENTRIES - 1; ns++) {
		for (int n = nums[ns][0]; n < nums[ns + 1][0] && n <= upton; n++) {
			for (int k = 0; k < nums[ns][1]; k++) {
				llu sum = 0;
				for (int i = 0; i < n && i <= k; i++) {
					sum += get_raw(n - 1, k - i);
				}
				if (n >= 3000) {
					others[n - 3000][k] = sum;
				}
				else {
					first3k[n][k] = sum;
				}
			}
		}
	}
}

llu perms_of_invs(int n, llu k, unsigned int hint) {
	const llu max_invs = ((llu)n * (llu)(n - 1)) / 2ULL;
	if (k > max_invs) {
		return 0;
	}
	if (k > max_invs / 2) {
		k = max_invs - k;
	}

	if (k >= (llu)hint) {
		return TOO_MUCH;
	}
	return get_raw(n, (int)k);
}

int main() {
	int n;
	llu k;
	scanf("%d %llu", &n, &k);
	k -= 1; // Convert to zero based index

	// Check: ((n - 1) * n) % 4 == 0
	if (n % 4 != 0 && n % 4 != 1) {
		puts("NIE");
		return 0;
	}

	make_tables(n);

	// Place numbers until we find a sensible range
	int atentry = NUMS_ENTRIES - 1;
	while (nums[atentry][0] > n) atentry--;
	llu reminvs = ((llu)(n - 1) * (llu)n) / 4ULL;

	if (perms_of_invs(n, reminvs, nums[atentry][1]) <= k) {
		puts("NIE");
		return 0;
	}

	init_tree(n);

	puts("TAK");
	for (; n > 1; n--) {
		while (nums[atentry][0] > n - 1) atentry--;
		auto work = [&](int i) -> bool {
			const auto poi = perms_of_invs(n - 1, reminvs - i, nums[atentry][1]);
			if (k < poi) {
				int nth = nth_in_tree(i);
				remove_in_tree(nth);
				printf("%d ", nth + 1);
				reminvs -= i;
				return true;
			}
			k -= poi;
			return false;
		};
		int i;
		const llu max_invs = ((llu)(n - 1) * (llu)(n - 2)) / 2ULL;
		if (max_invs < reminvs) {
			if (reminvs - max_invs < (llu)n) {
				i = (int)(reminvs - max_invs);
			}
			else {
				assert(false);
				// i = n;
			}
		}
		else {
			i = 0;
		}
		for (; i < n; i++) {
			if (work(i)) {
				goto loopend;
			}
		}

		assert(false);
	loopend:;
	}

	assert(reminvs == 0);
	printf("%d\n", nth_in_tree(0) + 1);

	return 0;
}