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
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

#define LL long long
#define INF 1000000000100000000
#define MAX_N 250090

vector<LL> P[MAX_N + 1];

inline LL maxPerm(int len) {
    return (LL)(len) * (len - 1) / 2;
}

inline LL perm(int len, LL inv) {
    LL ma = maxPerm(len);
    if(inv > ma) return 0;
    inv = min(inv, ma - inv);
    if((LL)P[len].size() <= inv) return INF;
    return P[len][inv];
}

void calcPerm() {
    P[0].push_back(1);
    P[1].push_back(1);
    for(int i = 2; i <= MAX_N; ++i) {
        LL jz = maxPerm(i) / 2;
        for(int j = 0; (LL)j <= jz; ++j) {
            P[i].push_back(0);
            for(int z = j, zz = max(0, j - i + 1); z >= zz; --z) {
                P[i][j] += perm(i - 1, z);
                if(P[i][j] >= INF) {
                    break;
                }
            }
            if(P[i][j] >= INF) {
                P[i].pop_back();
                break;
            }
        }
    }
}

class PowerTree {
    vector<int> data;

public:
    PowerTree(int n) {
        for(int i = 0; i < n; ++i) {
            data.push_back(0);
        }
    }

    void add(int i, int v) {
        while(i < int(data.size())) {
            data[i] += v;
            i += ((i ^ (i + 1)) + 1) / 2;
        }
    }

    int sum(int n) {
        int sum = 0;
        while(n >= 0) {
            sum += data[n];
            n -= ((n ^ (n + 1)) + 1) / 2;
        }
        return sum;
    }
};

int first_true(int n, function<bool(int)> func) {
    int ret = n;
    int l = 0, r = n - 1;
    while(l <= r) {
        int m = (l + r) / 2;
        if(func(m)) {
            ret = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0);

    calcPerm();

    int n;
    LL k;
    cin >> n >> k;
    --k;

    LL p = maxPerm(n) / 2;
    LL ma = maxPerm(n);
    if((ma & 1) || (k >= perm(n, p))) {
        cout << "NIE";
        return 0;
    }

    vector<int> ret;
    for(int i = 0; i < n; ++i) {
        for(int v = min(max(0LL, p - maxPerm(n-i-1)), (LL)(n - i)); v < n - i; ++v) {
            LL count = perm(n - i - 1, p - v);
            if(k < count) {
                ret.push_back(v);
                p -= v;
                break;
            } else {
                k -= count;
            }
        }
    }

    PowerTree tree(n);
    for(int a = 0; a < n; ++a) {
        tree.add(a, 1);
    }
    cout << "TAK\n";
    for(int v : ret) {
        int q = first_true(n, [&](int i) { return tree.sum(i) > v; });
        tree.add(q, -1);
        cout << q + 1 << " ";
    }


    return 0;
}