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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
typedef long long int lli;
using namespace std;

const int INF = 1e9 + 3;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
	int n, k, mn = INF, mx = -INF, pos_mn = -1, pos_mx = -1;
	cin >> n >> k;
	vector <int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
		mn = min(mn, a[i]);
		mx = max(mx, a[i]);
	}
	bool sorted = true, min_not_first = false, max_not_last = false;
	for (int i = 1; i < n; i++){
		sorted &= (a[i] > a[i - 1]);
		if (a[i] == mn){
			pos_mn = i;
			min_not_first = true;
		}
		if (a[i - 1] == mx){
			pos_mx = i - 1;
			max_not_last = true;
		}
	}
	if (sorted || (!min_not_first && !max_not_last && k == 3)){
		cout << "NIE\n";
		return 0;
	}
	
	vector <int> ans;
	if (k >= 3){
		if (min_not_first){
			ans.push_back(pos_mn);
			if (pos_mn != n - 1){
				ans.push_back(pos_mn + 1);
				k -= 3;
			} 
			else{
				k -= 2;
			}
			for (int i = 0; i < n; i++){
				if (k && (i != pos_mn - 1) && (i != pos_mn)){
					ans.push_back(i + 1);
					k--;
				}
			}
		}
		else if (max_not_last){
			ans.push_back(pos_mx + 1);
			if (pos_mx != 0){
				ans.push_back(pos_mx);
				k -= 3;
			} 
			else{
				k -= 2;
			}
			for (int i = 0; i < n; i++){
				if (k && (i != pos_mx - 1) && (i != pos_mx)){
					ans.push_back(i + 1);
					k--;
				}
			}
		}
		else{
			int where = -1;
			for (int i = 0; i < n - 1; i++){ 
				if (a[i] >= a[i + 1]){
					ans.push_back(i + 1);
					ans.push_back(i + 2);
					where = i + 1;
					break; // this must happen since the sequence isn't sorted
				}
			}
			k -= 3;
			for (int i = 0; i < n; i++){
				if (k && (i != where) && (i != where + 1)){
					ans.push_back(i + 1);
					k--;
				}
			}
		}
		cout << "TAK\n";
		sort(ans.begin(), ans.end());
		for (int x : ans){
			cout << x << " ";
		}
		cout << "\n";
	}
	else{ // k == 2, naive
		multiset <int> s;
		for (int i = 0; i < n; i++){
			s.insert(a[i]);
		}
		mn = INF;
		for (int i = 0; i < n - 1; i++){
			mn = min(mn, a[i]);
			s.erase(s.find(a[i]));
			if (mn >= *(s.rbegin())){
				cout << "TAK\n";
				cout << i + 1 << "\n";
				return 0;
			}
		}
		cout << "NIE\n";
	}
	
    return 0;
}