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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;


int main() {
  
  int N;
  ll K;
  cin >> N >> K;
  
  vector<unordered_map<ll, ll>> X(N+1); // X[number of digits][number of inversions] = #
  vector<ll> infty_beg(N+1);
  vector<ll> infty_end(N+1);
  
  X[1][0] = 1;
  
  ll elements = 1;
  
  for (int n = 2; n <= N; ++n) {
    elements += (n-1);
    //cerr << "n = " << n << ": (" << elements << ") " << endl;
    
    ll val = 0;
    
    for (ll i = 0; i < (elements+1)/2; ++i) {
      ll rev_i = elements - i - 1;
      
      auto itpr = X[n-1].find(i);
      if (itpr == X[n-1].end()) {
        //cerr << "noprev" << endl;
        infty_beg[n] = i;
        //cerr << "infty_beg[" << n << "] = " << i << endl;
        infty_end[n] = rev_i+1;
        break;
      }
      
      auto itppr = X[n-1].find(i-n);
      if (itppr != X[n-1].end())
        val -= itppr->second;
        
      val += itpr->second;
      
      if (val > 1e18 || val <0) {
        //cerr << "toobig [i=" << i << "]" << endl;
        infty_beg[n] = i;
        infty_end[n] = rev_i+1;
        break;
      }
        
      X[n][i] = val;
      X[n][rev_i] = val;
      
      //if (n > 8200 && n < 8300)
      //cerr << "X[" << n << "][" << i << "," << rev_i << "] = " << (ll) val << endl;
      /*int prev_i = i;
      if (i >= X[n-1].size()) {
        prev_i = X[n-1].size() * 2 - i -1;
        X[n].push_back(X[n][prev_i]);
      } else {          
        val += X[n-1][i];
        if (val > 1e18 || val <= 0) {
          max_i = i;
          break;
        }
        
        X[n].push_back(val);
      }
        
      cerr << X[n].back() << " ";*/
    }
    //cerr << endl;
  }
  
  set<int> E;
  for (int i = 1; i <= N; ++i) {
    E.insert(i);
  }
  
  ll XInv = (N-1)*N/2;
  
  if (XInv % 2) {
    cout << "NIE" << endl;
    return 0;
  }
  XInv /=2;
  
  if (infty_beg[N] <= XInv && XInv < infty_end[N]) {}
  else if (X[N][XInv] < K) {
    cout << "NIE" << endl;
    return 0;
  }
  
  //--K;
  
  cout << "TAK" << endl;
  
  for (int p = 0; p < N-1; ++p) {
    //cerr << "K=" << K << " p = " << p << endl;
    
    
    int i = 0;
    for (int x : E) {
      ll inv = XInv - i;
      ll cnt;
      //cerr << "infty: [" << infty_beg[N-p-1] << "; " << infty_end[N-p-1] << endl;
      if (infty_beg[N-p-1] <= inv && inv < infty_end[N-p-1])
        cnt = 2e18;
      else
        cnt = X[N-p-1][XInv - i];
      //cerr << " " << x << " ["<<(N-p-1) << ", " << (ll)(XInv-i) << "] #" << (ll)cnt << endl;
      if (cnt < K) {
        K -= cnt;
      } else {
        cout << x << ' ';
        E.erase(x);
        XInv -= i;
        break;
      }
      
      ++i;
    }
  }
  
  cout << *(E.begin()) << endl;
  return 0;
}