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

using namespace std;

#define INF 1000000000000000009LL

struct pair_hash {
	template <class T1, class T2>
	std::size_t operator () (const std::pair<T1,T2> &p) const {
		auto h1 = std::hash<T1>{}(p.first);
		auto h2 = std::hash<T2>{}(p.second);

		return (h1 * 937ull) ^ h2;  
	}
};

unordered_map<pair<int, long long>, long long, pair_hash> c;

// In how many ways we can get l inversions in n-permutation.
long long get(long long n, long long l){
	long long mx = n*(n-1)/2;
	long long half = mx/2;
	if (l>half) l = mx - l;
	if (l>200) return INF;
	if (l>20 && n>100) return INF;
	if (l>8 && n>1000) return INF;
	if (l==0) return 1;
	if (n==1) return 0;
	pair<int, long long> pp(n, l);
	auto it = c.find(pp);
	if (it != c.end()) return it->second;
	long long sum = 0;
	long long mm = n-1;
	if (l<mm) mm = l;
	for (long long i = 0; i <= mm; i++) {
		sum += get(n-1, l-i);
		if (sum > INF) {
			sum = INF;
			break;
		}
	}
	return c[pp] = sum;
}

set<int> remaining;

void init(int n){
	for(int i=0; i<n; i++){
		remaining.insert(i+1);
	}
}

int nth(size_t n){
	if(n>remaining.size()/2){
	//if(0){
		n = remaining.size() - n - 1;
		for(auto it = remaining.rbegin(); it!=remaining.rend(); it++){
			if(n-- == 0){
				int r = *it;
				remaining.erase(--it.base());
				return r;
			}
		}
	}
	else{
		for(auto it = remaining.begin(); it!=remaining.end(); it++){
			if(n-- == 0){
				int r = *it;
				remaining.erase(it);
				return r;
			}
		}
	}
	return -1;
}

void test(){
	for(long long n=1; n<200000; n++){
		int x=-1;
		for(int l=0; l<=n*(n-1)/2; l++){
			x = l;
			if(get(n, l)==INF){ break; }
		}
		printf("%lld %d\n", n, x);
	}
}

int main(){
	//test(); return 0;
	long long n;
	long long k;
	scanf("%lld %lld", &n, &k);
	k--;
	if((n*(n-1)) % 4){
		printf("NIE\n");
		return 0;
	}
	long long l = n*(n-1)/4;
	init(n);
	vector<int> ans;
	for(int i=0; i<n; i++){
		//printf("i=%d, l=%lld, k=%lld\n", i, l, k);
		bool found=false;
		long long n1 = n-i-1;
		long long min_inversions = l - (n1*(n1-1))/2;
		if(min_inversions<0)
			min_inversions = 0;

		int max_inversions = n-i-1;
		if(l<max_inversions){
			max_inversions = l;
		}

		long long k2 = k;
		for(int j=min_inversions; j<=max_inversions; j++){
			long long minus = get(n-i-1, l-j);
			//printf("  j=%d, minus=%lld\n", j, minus);
			long long k3 = k2 - minus;
			if(k3<0){
				found = true;
				k = k2;
				l -= j;
				//printf("%dth\n", j);
				ans.push_back(nth(j));
				break;
			}
			k2 = k3;
		}
		if(!found){
			printf("NIE\n");
			return 0;
		}
	}
	printf("TAK\n");
	for(auto a: ans)
		printf("%d ", a);
	printf("\n");
	return 0;
}