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

#define endl '\n'
#define ll long long
#define pli pair<long long, int>
#define st first
#define nd second

using namespace std;

int n, k;
const int MAX_N = 500100;
ll tree[2*MAX_N];
vector<bool> result(MAX_N);

void build(){
    for(int i=n-1; i>0; i--) tree[i] = max(tree[i<<1], tree[i<<1|1]);
}

ll query(int l, int r){
    ll res = 0;
    for(l += n, r += n; l < r; l>>=1, r>>=1){
        if(l&1) res = max(res, tree[l++]);
        if(r&1) res = max(res, tree[--r]);
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    for(int i=0; i<n; i++){
        cin >> tree[i+n];
    }
    build();
    ll min_val = 1000000100;
    int best_i = 0;
    int best_k = 500100;
    for(int i=n; i<2*n-1; i++){
        if(tree[i] >= tree[i+1]){
            // cout << i << endl;
            int tmp_k = 4;
            ll a = tree[i];
            if(i != n){
                if(min_val >= tree[i+1]){
                    a = min_val;
                    tmp_k--;
                }
            } else tmp_k--;
            if(i != 2*n-2){
                ll max_val = query(i+2-n, n);
                if(max_val <= a){
                    tmp_k--;
                }
            } else tmp_k--;

            if(tmp_k < best_k){
                best_k = tmp_k;
                best_i = i;
            }
        }
        min_val = min(min_val, tree[i]);
    }
    if(best_k > k){
        cout << "NIE" << endl;
    } else {
        cout << "TAK" << endl;
        min_val = 1000000100;
        for(int i=n; i<2*n-1; i++){
            if(i == best_i){
                // cout << "best_i: " << i-n << endl;
                result[i-n] = true;
                ll a = tree[i];

                if(i != n) {
                    if(min_val >= tree[i+1]){
                        result[i-1-n] = false;
                        a = min_val;
                    } else {
                        result[i-1-n] = true;
                    }
                }
                if(i != 2*n-2){
                    ll max_val = query(i+2-n, n);
                    if(max_val <= a){
                        result[i+1-n] = false;
                    } else {
                        result[i+1-n] = true;
                    }
                }
                // cout << result[i-1-n] << " " << result[i-n] << " " << result[i+1-n] << endl;
                break;
            }
            min_val = min(min_val, tree[i]);
        }
        k -= best_k;
        for(int i=n; i<2*n; i++){
            if(result[i-n] != true && k > 0){
                cout << i-n+1 << " ";
                k--;
            } else if(result[i-n] == true){
                cout << i-n+1 << " ";
            }
        }
        cout << endl;
    }
   

    return 0;
}