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
#include<iostream>
#include<vector>
#include<unordered_map>

#define REP(i, n) for(int i=0; i<(n); i++)

#define FOR(i, a, b) for(int i=(a); i <= (b); i++)

using namespace std;

typedef long long llint;

unordered_map<llint,int> Tm;

inline llint key(int n, int k) { return (((llint)n) << 32) + k; }

llint ninv(int n, int k) {
  if (n <= 0 || k < 0) return 0;
  if (k == 0) return 1;
  auto it = Tm.find(key(n,k));
  if (it != Tm.end()) {
    return it->second;
  }
  llint ret = 0;
  REP(i, n) {
    ret += ninv(n-1, k-i);
  }
  Tm[key(n,k)] = ret;
  //cout << "ninv(n="<<n<<",k="<<k<<") ret="<<ret<<endl;
  return ret;
}

int main(void) {
  int n;
  llint p;
  cin >> n;
  cin >> p;
  p--;

  if (n % 4 > 1) { cout << "NIE"; return 0; }

  int k = n*(n-1) / 4;
  int k0 = k;

  vector<int> vv, pp;
  vv.resize(n + 1);
  pp.resize(n + 1);

  FOR(i, 1, n) {
    int q = 0;
    FOR(a, 1, n) {
      //cout << "i="<<i<<" q=" << q <<" a="<<a << " vv[a]="<<vv[a]
      //     << " k=" << k << " p=" << p << endl;
      if (vv[a]) {
        // q++;
      } else {
        pp[i] = a;
        llint L = ninv(n-i, k - q);
        //cout << "L=" << L << endl;
        if (p >= L) {
          p -= L;
          q++;
          continue;
        }
        break;
      }
    }  
    k -= q;
    vv[pp[i]] = 1;
  }
  //cout << "p="<<p<<endl;
  if (p != 0) { cout << "NIE"; return 0; }

  int r = 0;
  FOR(i, 1, n-1) FOR(j, i+1, n) if (pp[i] > pp[j]) r+=1;
  //cout << "r=" << r << endl;
  if (r != k0) { cout << "NIE"; return 0; }

  cout << "TAK" << endl;
  FOR(i, 1, n) {
    if (i > 1) cout << " ";
    cout << pp[i];
  }
  cout << endl;

  return 0;
}