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

using namespace std;

const int N = 250005, BASE = 262144;

int tree[2 * BASE + 1];
int n;
long long K;
vector<long long> dp[N];

long long calcInverse(int n) {
    return (long long)n * (n - 1) / 2;
}

void remove(int pos) {
    pos += BASE;
    while (pos >= 1) {
        tree[pos]--;
        pos /= 2;
    }
}

int query(int pos, int value) {
    if (pos >= BASE) {
        return pos - BASE;
    }
    if (tree[2 * pos] >= value) {
        return query(2 * pos, value);
    } else {
        return query(2 * pos + 1, value - tree[2 * pos]);
    }
}

void add(long long &w, int x, long long y) {
    y = min(y, calcInverse(x) - y);
    if (y >= 0 && y < (long long)dp[x].size()) {
        w += dp[x][y];
    } else if (y >= (long long)dp[x].size() && y <= calcInverse(x) / 2) {
        w = K;
    }
}

int main() {
    
    scanf("%d %lld", &n, &K);
    
    dp[0].push_back(1LL);
    for (int i = 1; i <= n; i++) {
        long long prefInv = calcInverse(i);
        for (long long j = 0; j <= prefInv / 2; j++) {
            long long tmp = 0;
            for (int k = 0; k < i && j - k >= 0; k++) {
                add(tmp, i - 1, j - k);
                if (tmp >= K) {
                    break;
                }
            }
            if (tmp >= K) {
                break;
            }
            dp[i].push_back(tmp);
        }
    }

    if (calcInverse(n) % 2 != 0 || (calcInverse(n) / 2 < (long long)dp[n].size() && dp[n][calcInverse(n) / 2] < K)) {
        printf("NIE\n");
        return 0;
    }
    
    for (int i = 1; i <= n; i++) {
        tree[i + BASE] = 1;
    }
    for (int i = BASE - 1; i >= 1; i--) {
        tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
    
    printf("TAK\n");
    long long inv = calcInverse(n) / 2;
    for (int i = n; i >= 1; i--) {
        long long prevInv = calcInverse(i - 1);
        long long start = max(0LL, inv - prevInv);
        for (long long j = start; j < i; j++) {
            long long remainingInv = inv - j;
            remainingInv = min(remainingInv, prevInv - remainingInv);
            if ((long long)dp[i - 1].size() <= remainingInv || dp[i - 1][remainingInv] >= K) {
                int nextElement = query(1, j + 1);
                printf("%d ", nextElement);
                remove(nextElement);
                inv -= j;
                break;
            }
            K -= dp[i - 1][remainingInv];
        }
    }
    
    return 0;
}