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
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N=500005,inf=1000000010;
int n,k,i,pos,a[N],pre[N],suf[N],cut[N];
void TAK(){
	puts("TAK");
	for(i=1;i<n;i++)if(cut[i])k--;
	for(i=1;i<n&&k>1;i++)if(!cut[i])cut[i]=1,k--;
	for(i=1;i<n;i++)if(cut[i])printf("%d ",i);
	exit(0);
}
void NIE(){
	puts("NIE");
	exit(0);
}
int main(){
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<n;i++)if(a[i]>=a[i+1]){pos=i;break;}
	if(!pos)NIE();
	for(pre[0]=inf,i=1;i<=n;i++)pre[i]=min(pre[i-1],a[i]);
	for(i=n;i;i--)suf[i]=max(suf[i+1],a[i]);
	if(k==2){
		for(i=1;i<n;i++)if(pre[i]>=suf[i+1]){
			cut[i]=1;
			TAK();
		}
		NIE();
	}
	if(k>=4){
		cut[pos-1]=cut[pos]=cut[pos+1]=1;
		TAK();
	}
	for(i=2;i<=n;i++)if(a[i]==pre[n]){
		cut[i-1]=cut[i]=1;
		TAK();
	}
	for(i=1;i<n;i++)if(a[i]==suf[1]){
		cut[i-1]=cut[i]=1;
		TAK();
	}
	NIE();
}