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
#include <bits/stdc++.h>
using namespace std;
struct st{
		int val, i;
		st(){}
		st(int val, int i) : val(val), i(i) {}
		void Max(st a, st b){
				if(a.val > b.val) val = a.val, i = a.i;
				else val = b.val, i = b.i;
		} void Min(st a, st b){
				if(a.val > b.val) val = b.val, i = b.i;
				else val = a.val, i = a.i;
		}
};
void nie(){ printf("NIE\n"); exit(0); }

int main(){
		int n, k;
		scanf("%d%d", &n, &k);
		vector<int> t(n);
		vector<st> smax(n), pmin(n);
		for(int i = 0; i < n; ++i) scanf("%d", &t[i]);
		smax[n-1] = st(t[n-1], n-1), pmin[0] = st(t[0], 0);
		for(int i = 1; i < n-1; ++i) pmin[i].Min(st(t[i], i), pmin[i-1]);
		for(int i = n-2; ~i; --i) smax[i].Max(st(t[i], i), smax[i+1]);
		
		if(k == 2){
				for(int i = 0; i < n-1; ++i) if(pmin[i].val >= smax[i+1].val){ printf("TAK\n%d\n", i+1); return 0; }
				nie();
		} else if(k == 3){
				if(t[0] >= smax[1].val){printf("TAK\n%d %d\n", 1, 2); return 0;}
				else if(pmin[n-2].val >= t[n-1]){printf("TAK\n%d %d\n", n-2, n-1); return 0;}
				for(int i = 1; i < n-1; ++i) if(pmin[i-1].val >= t[i] || t[i] >= smax[i+1].val){ printf("TAK\n%d %d\n", i, i+1); return 0;}
				if(t[0] >= t[n-1]){ printf("TAK\n%d %d\n", 1, n-1); return 0;}
				nie();
		} else if(k >= 4){
				vector<int> odp;
				vector<bool> used(n+1);
				int ile = k-4; bool b = 0;
				for(int i = 0; i < n-1; ++i) if(t[i] >= t[i+1]){
						if(!i) used[i+1] = 1, used[i+2] = 1, used[i+3] = 1;
						else if(i == n-2) used[i-1] = 1, used[i] = 1, used[i+1] = 1;
						else used[i] = 1, used[i+1] = 1, used[i+2] = 1;
						b = 1; break;
				}
				if(!b) nie();
				printf("TAK\n");
				for(int i = 1; i < n; ++i){
						if(ile && !used[i]) used[i] = 1, --ile;
						if(used[i]) printf("%d ", i+1);
				}
		}
		
		return 0;
}