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
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;

typedef unsigned long long llu;
typedef pair<int, int> ii;

using namespace __gnu_pbds;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const llu INF = 1e18;

vector<llu> V[250007];
ordered_set S;

inline llu cnt(llu n, llu k) {
    llu tmp = n * (n - 1LL) >> 1;
    if(k > tmp)
        return 0;
    if(V[n].size() >= k + 1LL)
        return V[n][k];
    if(V[n].size() >= tmp - k + 1LL)
        return V[n][tmp - k];
    return INF + 1LL;
}

int main() {
    V[1].push_back(1);
    for(llu n = 2LL ; n <= 250000LL ; n++) {
        llu last = n * (n - 1LL) / 2LL / 2LL;
        V[n].push_back(1LL);
        for(llu k = 1LL ; k <= last ; k++) {
            llu tmp = V[n][k - 1];

            if(V[n - 1LL].size() < k + 1) {
                if(k <= (n - 2LL) * (n - 1LL) / 2LL / 2LL)
                    break;
                if(k <= (n - 2LL) * (n - 1LL) / 2LL)
                    tmp += V[n - 1LL][(n - 2LL) * (n - 1LL) / 2LL - k];
            } else
                tmp += V[n - 1LL][k];

            if(k >= n)
                tmp -= V[n - 1LL][k - n];

            if(tmp > INF)
                break;

            V[n].push_back(tmp);
        }
    }

    llu n, k;
    scanf("%llu %llu", &n, &k);

    llu inv = n * (n - 1) / 2 / 2;
    if(((n * (n - 1)) % 4LL) || cnt(n, inv) < k) {
        printf("NIE\n");
        return 0;
    }

    for(int i = 1 ; i <= n ; i++)
        S.insert(i);

    printf("TAK\n");
    for( ; n >= 1LL ; n--) {
        llu first = 1, sum = 0;
        llu tmp = cnt(n - 1, inv - first + 1);

        if(tmp == 0) {
            first = inv + 1 - (n - 1) * (n - 2) / 2LL;
            tmp = cnt(n - 1, inv - first + 1);
        }

        while(sum + tmp < k) {
            sum += tmp;
            first++;
            tmp = cnt(n - 1, inv - first + 1);
        }

        printf("%d ", *S.find_by_order(first - 1));
        S.erase(S.find_by_order(first - 1));
        k -= sum;
        inv = inv - first + 1;
    }
    printf("\n");

    return 0;
}