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

const int MAX_N = 5e5;
int n, k;

bool res[MAX_N+3];
int a[MAX_N+3];

bool is_increasing() {
	for (int i = 1; i < n; i++) 
		if (a[i] <= a[i-1]) return false;	
	return true;
}

std::vector<int> min_pref, max_suf;

bool go_2() {
	for (int i = 0; i < n-1; i++) 
		if (min_pref[i] >= max_suf[i+1]) {
			res[i] = true;
			return true;
		}
	return false;
}

bool go_3() {
	for (int i = 1; i < n-1; i++) {
        if (min_pref[i-1] >= a[i] || a[i] >= max_suf[i+1]) {
            res[i-1] = res[i] = true;
            return true;
        }
    }
    return false;
}

void go_4() {
	for (int i = 1; i < n-2; i++) 
		if (a[i] >= a[i+1]) {
			res[i-1] = res[i] = res[i+1] = true;
			return;
		}
	return;
}

void output() {
	int m = 1;
	for (int i = 0; i < n-1; i++) 
		if (res[i]) m++;
	int left = k-m;
	for (int i = 0; i < n-1; i++) 
		if (!res[i] && left > 0) {
			res[i] = true;
			left--;			
		}
	std::cout << "TAK\n";
	for (int i = 0; i < n-1; i++) 
		if (res[i]) std::cout << i+1 << " ";
	std::cout << "\n";
}

int main() {
	std::ios_base::sync_with_stdio(0); std::cin.tie(NULL);
	std::cin >> n >> k;
	for (int i = 0; i < n; i++) std::cin >> a[i];
	
	if (is_increasing()) {
		std::cout << "NIE\n";
		return 0;
	}

	min_pref.resize(n, 0);
	max_suf.resize(n, 0);
	min_pref[0] = a[0];
	for (int i = 1; i < n; i++) min_pref[i] = std::min(min_pref[i-1], a[i]);
	max_suf[n-1] = a[n-1];
	for (int i = n-2; i >= 0; i--) max_suf[i] = std::max(max_suf[i+1], a[i]);

	if (k >= 2 && go_2()) {
		output();
	} else if (k >= 3 && go_3()) {
		output();
	} else if (k >= 4) {
		go_4();
		output();
	} else {
		std::cout << "NIE\n";
	}
}