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
#include<iostream>
#include<list>
#include<stdio.h>
#include<map>
#include<set>
#include<list>
#include<vector>
using namespace std;
#define ull long long int
#define FOR(i,n) for(int i=0;i<n;++i)
#define FORD(i,n) for(int i=(n)-1;i>=0;--i)
ull inline min(ull a,ull b){return a>b?b:a;}
ull inline max(ull a,ull b){return a<b?b:a;}
#define dcout 0 && cout
#define dcerr 0 && cout
ull**m;
ull maxValue=1000000000LL*1000000000LL+10;
int limit=50;

ull getM(ull pairs, ull row) {
	ull totalPairs = row * (row - 1LL) / 2;
	if (pairs > totalPairs) return 0;
	ull realColumn = min(pairs, totalPairs - pairs);
	if (realColumn >= limit) return maxValue;
	return m[row][realColumn];
}
int first(int**heap){
	int level=20;
	int node=0;
	while(level){
		node*=2;
		--level;
		if(!heap[level][node])++node;
	}
	return node;
}
int forward(int**heap,int current, int skip){
	int level=0;
	while(1){
		if(current&1){
			++level;
			current/=2;
		}else{
			if(heap[level][current+1]<skip){
				skip-=heap[level][current+1];
				++level;
				current/=2;
			}else{
				++current;
				break;
			}
		}
	}
	while(level){
		--level;
		current*=2;
		if(heap[level][current]<skip){
			skip-=heap[level][current];
			++current;
		}
	}
	return current;
}
void erase(int**heap,int current){
	FOR(i,20){
		--heap[i][current];
		current/=2;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int rows=260000;
	int columns=limit;
	m=new ull*[rows];
	*m=new ull[rows*columns];
	FOR(i,rows*columns)m[0][i]=0;
	FOR(i,rows)m[i]=*m+i*columns;
	ull n, k;
	cin>>n>>k;

	m[0][0] = 1;
	m[1][0] = 1;
	m[1][1] = 0;
	m[2][0] = 1;
	m[2][1] = 1;
	for (int i = 3; i < rows; i++) {
		ull pairs = i * (i - 1LL) / 2;

		m[i][0] = 1;
		for (int j = 1; j <= min(pairs, limit-1); j++) {
			if(m[i][j-1]>=maxValue){m[i][j]=maxValue;continue;}
			m[i][j] = m[i][j - 1] + m[i - 1][j] - (j - i >= 0 ? m[i - 1][j - i] : 0);
			if(m[i][j]>=maxValue){m[i][j]=maxValue;continue;}
		}
	}
	ull pairs = (n - 1LL) * n / 4;

	int*numbers=new int[n];
	int**heap=new int*[20];
	int e=n;
	heap[0]=new int[n+10];
	FOR(j,n)heap[0][j]=1;
	FOR(j,10)heap[0][n+j]=0;
	FOR(i,19){
		e=(e+1)/2;
		heap[i+1]=new int[e+10];
		FOR(j,e)heap[i+1][j]=heap[i][2*j]+heap[i][2*j+1];
		FOR(j,10)heap[i+1][e+j]=0;
	}
	for (int i = 0; i < n; i++) {
		numbers[i]=(i + 1);
	}
	if (((n - 1LL) * n / 2) % 2 == 0 && getM(pairs, n) >= k) {
		cout<<"TAK\n";
		for (int i = n - 1; i >= 0; i--) {
			int digitIterator = first(heap);
			long long int pi=i*(i-1LL)/2;
			long long int skok=((long long int)pairs)-pi-1;
			if(getM(pairs,i)<k && skok>0){
				digitIterator = forward(heap,digitIterator,(int)skok);
				pairs-=skok;
			}
			while (getM(pairs, i) < k) {
				digitIterator=forward(heap,digitIterator,1);
				k -= getM(pairs, i);
				--pairs;
			}

			cout<<(digitIterator+1)<<" ";
			erase(heap,digitIterator);
		}
		cout<<endl;
	} else cout<<"NIE\n";

	return 0;
}