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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 50;

int n, k, a[N], mx[N], mn[N];

void impossible() {
	cout << "NIE\n";
}

void gogo(vector<int> ret) {
	assert(ret.size() < k);
	static int b[N];
	for (int i = 1; i <= n; ++i)
		b[i] = 0;
	for (int x : ret)
		b[x] = 1;
	int p = 1;
	while (ret.size() + 1 < k) {
		while (b[p]) ++p;
		ret.push_back(p);
		b[p] = 1;
	}
	cout << "TAK\n";
	sort(ret.begin(), ret.end());
	for (int i = 0; i < ret.size(); ++i)
		cout << ret[i] << " \n"[i + 1 == ret.size()];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	bool ok = false;
	for (int i = 1; i + 1 <= n; ++i) {
		if (a[i] >= a[i + 1]) {
			ok = true;
			break;
		}
	}
	if (!ok) {
		cout << "NIE" << '\n';
		return 0;
	}
	if (k >= 4) {
		for (int i = 1; i + 1 <= n; ++i) {
			if (a[i] >= a[i + 1]) {
				vector<int> ret;
				ret.push_back(i);
				if (i > 1) ret.push_back(i - 1);
				if (i + 1 < n) ret.push_back(i + 1);
				gogo(ret);
				return 0;
			}
		}
		throw;
	}
	if (k >= 3) {
		int mx_p = max_element(a + 1, a + n) - a;
		int mn_p = min_element(a + 2, a + n + 1) - a;
		if (a[n] <= a[mx_p]) {
			if (mx_p == 1)
				gogo({1});
			else if (mx_p == n)
				gogo({mx_p - 1});
			else
				gogo({mx_p - 1, mx_p});
			return 0;
		}
		if (a[1] >= a[mn_p]) {
			if (mn_p == 1)
				gogo({1});
			else if (mn_p == n)
				gogo({mn_p - 1});
			else
				gogo({mn_p - 1, mn_p});
			return 0;
		}
	}
	mn[1] = a[1];
	for (int i = 2; i <= n; ++i)
		mn[i] = min(mn[i - 1], a[i]);
	mx[n] = a[n];
	for (int i = n - 1; i >= 1; --i)
		mx[i] = max(mx[i + 1], a[i]);
	for (int i = 1; i < n; ++i) {
		if (mn[i] >= mx[i + 1]) {
			gogo({i});
			return 0;
		}
	}
	impossible();
	return 0;
}