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

int main() {
	int n;
	long long k;
	scanf("%d", &n);
	scanf("%lld", &k);
	long long triangle[25][212];
	for (int i = 0; i < 25; i++) for (int j = 0; j < 212; j++)
		triangle[i][j] = 0;
	triangle[0][0] = 1;
	int max = 210;
	if ((n / 2 * 2) % 4 != 0) {
		printf("NIE\n");
		return 0;
	}
	for (int i = 1; i < n + 1; i++) {
		triangle[i][0] = 1;
		for (int j = 1; j < max; j++) {
			triangle[i][j] = triangle[i - 1][j] + triangle[i][j - 1];
			if (triangle[i][j] >= 9000000000000000000L || triangle[i][j] < 0) {
				max = j;
				break;
			}
			if (j > i) {
				triangle[i][j] -= triangle[i - 1][j - i - 1];
			}
		}
	}
	int most_inversions[92683];
	most_inversions[3] = 1;
	most_inversions[4] = 3;
	int inc = 2;
	for (int i = 5; i < 92683; i++) {
		if ((i + 1) % 4 == 0 || i % 4 == 0) inc++;
		most_inversions[i] = most_inversions[i - 1] + inc;
	}
	if (n < 23) {
		int row = n - 2;
		inc = 2;
		int q = 1;
		most_inversions[3] = 1;
		most_inversions[4] = 3;
		std::vector<int> in;
		while (q <= n) {
			in.push_back(q++);
		}
		int y = most_inversions[n - 1] + n / 2;
		int x = most_inversions[n - 1] - (n - 1) / 2;
		long long s2 = 0l;
		for (int i = x; i <= y; i++) {
			s2 += triangle[row][i];
		}
		if (k > s2) {
			printf("NIE\n");
			return 0;
		}
		printf("TAK\n");
		int inversions = 0;
		while (row > 0) {
			long long sum = 0;
			int i;
			for (i = x; i <= y && sum + triangle[row][i] < k; i++) {
				sum += triangle[row][i];
			}
			int value = row - (y - i) + 1;
			inversions += value;
			int mine = in[value];
			printf("%d ", mine);
			in.erase(in.begin() + value);

			if (i > 2 && i > most_inversions[i + 1]) {
				int a = i - most_inversions[i + 1];
				if (triangle[row][most_inversions[i + 1]] == triangle[row][most_inversions[i + 1] + 1]) {
					a--;
				}
				y = most_inversions[i + 1] - a;
			}
			else {
				y = i;
			}
			x = std::max(0, y - row);
			k = k - sum;
			row--;
		}

		if (in.size() == 2 && inversions == most_inversions[n]) {
			printf("%d %d", in[0], in[1]);
		}
		else if (in.size() == 2) {
			printf("%d %d", in[1], in[0]);
		}
		printf("\n");
	}
	else {
		printf("NIE\n");
	}
	return 0;
}