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
#include <bits/stdc++.h>
using namespace std;

#define REP(i, n) for (int i=0, ___=(n); i<___; ++i)
#define FOR(i, a, b) for (int i=(a), ___=(b); i<=___; ++i)

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<int, ll> PIL;

int read() { int n; cin >> n; return n; }

const ll mm = 1000000000000000001LL;

vector<vector<ll> > v;

void foo(int n, ll k, int inv, set<int> &s) {
	while (n > 2) {
		for (set<int>::iterator it = s.begin(); it != s.end(); ++it) {
			ll cur = inv < v[n-1].size() ? v[n-1][inv] : v[n-1].back() == 1 ? 0 : mm;
			if (k > cur) {
				k -= cur;
				--inv;
				continue;
			}
			cout << *it << " ";
			s.erase(it);
			break;
		}
		--n;
	}
	if (n == 1) {
		cout << *s.begin() << "\n";
		return;
	}
	int a = *s.begin();
	int b = *s.rbegin();
	if (inv == 0) {
		cout << a << " " << b << "\n";
		return;
	}
	cout << b << " " << a << "\n";
	return;
}

int main() {
	int n = read();
	ll k; cin >> k;

	if (n % 4 == 2 || n % 4 == 3) {
		cout << "NIE\n";
		return 0;
	}

	v.push_back(vector<ll>());
	v.push_back(vector<ll>(1, 1));
	FOR(nn, 2, n) {
		v.push_back(vector<ll>(1, 1));
		FOR(inv, 1, 1LL * nn * (nn-1) / 2) {
			ll up = inv < v[nn-1].size() ? v[nn-1][inv] : v[nn-1].back() == 1 ? 0 : mm;
			ll down = inv >= nn ? v[nn-1][inv - nn] : 0;
			ll cur = v[nn][inv-1] + up - down;
			if (cur > mm) cur = mm;
			v[nn].push_back(cur);
			if (cur == mm) break;
		}
	}

	ll inv = 1LL * n * (n-1) / 4;
	ll cnt = inv < v[n].size() ? v[n][inv] : mm;

	if (k > cnt) {
		cout << "NIE\n";
		return 0;
	}

	cout << "TAK\n";

	set<int> s;
	REP(i, n) s.insert(i+1);
	foo(n, k, inv, s);

	return 0;
}