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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, l, r) for (auto i = (l); i <= (r); ++i)
#define REP(i, n) FOR (i, 0, (n)-1)
#define ssize(x) int(x.size())
template<class A, class B>
auto&
operator<<(ostream& o, pair<A, B> p)
{
  return o << "(" << p.first << ", " << p.second << ")";
}
template<class T>
auto
operator<<(ostream& o, T x) -> decltype(x.end(), o)
{
  o << "{";
  int i = 0;
  for (auto e : x) o << (", ") + 2 * !i++ << e;
  return o << "}";
}
#ifdef DEBUG
#define debug(x...)                                                            \
  cerr << "[" #x "]: ", [](auto... $) { ((cerr << $ << "; "), ...); }(x),      \
    cerr << '\n'
#else
#define debug(...)                                                             \
  {                                                                            \
  }
#endif

// Variables
int n, k;
vector<int> seq;

void
output(int first, int count)
{
  debug(first, count);
  k -= count + 1;
  cout << "TAK\n";
  int x = 1;
  for (; x < first && k; ++x, --k) cout << x << " ";      // separators before first
  for (x = first; count; ++x, --count) cout << x << " ";  // core separators
  for (; k; ++x, --k) cout << x << " ";                   // the rest
  cout << "\n";
}

int
main()
{
  cin.tie(0)->sync_with_stdio(0);

  // Input
  cin >> n >> k;
  seq.resize(n);
  for (auto& x : seq) cin >> x;

  // Calculate min on prefix and max on suffix
  vector<int> pmin(n), smax(n);
  pmin[0] = seq[0];
  smax[n - 1] = seq[n - 1];
  for (int x = 1; x < n; ++x) pmin[x] = min(seq[x], pmin[x - 1]);
  for (int x = n - 2; x >= 0; --x) smax[x] = max(seq[x], smax[x + 1]);

  // If it works for k = 2, it works for any k
  for (int x = 1; x < n; ++x)
    if (pmin[x - 1] >= smax[x])
    {
      output(x, 1);
      return 0;
    }
  if (k == 2)
    goto bad;

  // If it works for k = 3, it works for any k >= 3
  for (int x = 1; x + 1 < n; ++x)
    if (seq[x] <= pmin[x - 1] || seq[x] >= smax[x + 1])
    {
      output(x, 2);
      return 0;
    }
  if (k == 3) goto bad;

  // Check for k >= 4
  for (int x = 2; x + 1 < n; ++x)
    if (seq[x - 1] >= seq[x])
    {
      output(x - 1, 3);
      return 0;
    }

bad:
  cout << "NIE\n";
  return 0;
}