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
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

typedef long long i64;

const int N = 250000 + 10;
const i64 INF = 0x3f3f3f3f3f3f3f3fLL;

std::vector<i64> f[N];

inline void add(i64 &lhs, i64 rhs) { lhs = std::min(lhs + rhs, INF); }

i64 get(int n, i64 m) {
  i64 t = std::min(m, n * (n - 1LL) / 2 - m);
  if (t < 0) return 0;
  return t < f[n].size() ? f[n][t] : INF;
}

int n;
i64 k;

tree<int, null_type, std::less<int>, rb_tree_tag, tree_order_statistics_node_update> pool;

int main() {
  scanf("%d%lld", &n, &k);
  i64 m = n * (n - 1LL) / 2;
  if (m & 1) {
    puts("NIE");
    return 0;
  }
  m >>= 1;
  f[0].push_back(1);
  for (int i = 0; i < n; ++i) {
    int tot = f[i].size() + (f[i].back() == INF ? 0 : i);
    f[i + 1].resize(tot);
    for (int j = 0; j < f[i].size(); ++j)
      for (int k = 0; k <= i && j + k < tot; ++k)
        add(f[i + 1][j + k], f[i][j]);
    for (int j = 0; j < tot; ++j) {
      if (f[i + 1][j] == INF) {
        f[i + 1].resize(j + 1);
        break;
      }
    }
  }
  if (get(n, m) < k) {
    puts("NIE");
    return 0;
  }
  for (int i = 1; i <= n; ++i) pool.insert(i);
  puts("TAK");
  for (int i = n; i > 0; --i) {
    int j = std::max(m - (i - 1LL) * (i - 2LL) / 2, 0LL);
    for (auto it = pool.find_by_order(j); it != pool.end(); ++it, ++j) {
      i64 temp = get(i - 1, m - j);
      if (temp >= k) {
        printf("%d ", *it);
        pool.erase(it);
        m -= j;
        break;
      } else {
        k -= temp;
      }
    }
  }
  return 0;
}