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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
const ll infty = (ll)(3e18) + 5;
const int N = 250005;

vector<ll> dp[N];
ll f(ll n, ll k)
{
  if (k < 0 || k > n*(n-1)/2LL) return 0;
  if (k < (ll) dp[n].size()) return dp[n][k];
  if (n*(n-1)/2LL - k < (ll) dp[n].size()) return dp[n][n*(n-1)/2LL - k];
  return infty;
}

int main()
{
  dp[0].push_back(1);
  for (int n = 1; n < N; n++)
  {
    dp[n].reserve(10);
    dp[n].push_back(1);
    for (ll k = 1; k <= 1LL*n*(n-1)/2LL; k++)
    {
      ll val = 0;
      for (ll i = max(0LL, k-n+1); i <= k; i++)
      {
        val += f(n-1,i);
        if (val >= infty)
        {
          val = infty;
          break;
        }
      }
      dp[n].push_back(val);
      if (dp[n].back() >= infty) break;
    }
  }

  ll n; ll kta; scanf("%lld%lld", &n, &kta);
  if (n * (n-1) % 4LL != 0) { puts("NIE"); return 0; }
  if (f(n,n*(n-1)/4LL) < kta) { puts("NIE"); return 0; }
  printf("TAK\n");

  tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> S;
  for (int i = 1; i <= n; i++) S.insert(i);

  ll k = n * (n-1) / 4LL;
  for (int i = 1; i <= n; i++)
  {
    ll nn = n - i + 1;
    for (int co = max(1LL, k+1-(nn-1)*(nn-2)/2LL); co <= nn; co++)
    {
      ll xd = f(nn-1, k-co+1);
      if (xd >= kta)
      {
        auto xdd = S.find_by_order(co-1);
        printf("%d ", *xdd);
        S.erase(xdd);
        k = k-co+1;
        break;
      }
      else
        kta -= xd;
    }
  }
  printf("\n");

  return 0;
}