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
// PA2017, Permutacje
// Andrzej Pezarski

#include <cstdio>
#include <vector>
using namespace std;

const long long INF=1000000000000000001LL;

struct Drzewko {
    int L;
    vector<int> T;
    
    Drzewko(int n) {
        L=1;
        while (L<n) L*=2;
        T.resize(2*L);
        for (int i=L; i<2*L; i++) T[i]=1;
        for (int i=L-1; i>0; i--) T[i]=T[2*i]+T[2*i+1];
    }
    
    int f(int k) {
        int v=1;
        while(v<L) {
            T[v]--;
            if (T[2*v]<=k) {
                k-=T[2*v];
                v=2*v+1;
            } else v=2*v;
        }
        T[v]--;
        return v-L;
    }
};

struct Tabelka {
    vector<vector<long long> > T;
    Tabelka(long long N) {
        T.resize(N+1);
        T[1].push_back(1);
        for (long long n=2; n<=N; n++) {
            long long maxI=n*(n-1)/2;
            long long sum=0;
            for (int a=-n, b=0; b<=maxI; a++, b++) {
                sum+=((a>=0&&a<T[n-1].size())?-T[n-1][a]:0LL)+(b<T[n-1].size()?T[n-1][b]:0LL);
                sum=min(sum, INF);
                T[n].push_back(sum);
                if (sum==INF) break;
            }
        }
    }
    long long f(long long n, long long i){
        long long maxI=n*(n-1)/2;
        i=min(i, maxI-i);
        if (i<0) return 0LL;
        if (i>=T[n].size()) return INF;
        return T[n][i];
    }
};



int main() {
    long long N;
    long long K;
    scanf("%lld%lld", &N, &K);
    if ((N*(N-1)/2)%2) {
        printf("NIE\n");
        return 0;
    }
    long long I=N*(N-1)/4;
    Tabelka T(N);
    if (T.f(N, I)<K){
        printf("NIE\n");
        return 0;
    }
    vector<int> RES;
    Drzewko D(N);
    while(N>1) {
        long long maxI2=(N-1)*(N-2)/2;
        long long i=max(0LL, I-maxI2);
        I-=i;
        while (T.f(N-1, I)<K) {
            K-=T.f(N-1, I);
            i++;
            I--;
        }
        RES.push_back(i);
        N--;
    }
    RES.push_back(0);
    printf("TAK\n");
    for (int i=0; i<RES.size(); i++) {
        printf("%d ", D.f(RES[i])+1);
    }
    printf("\n");
    return 0;    
}