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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector<int> result;


int sol_for_2(vector<int> &vec, int a, int b) {
    map<int, int> mapa1;
    mapa1[vec[a]] = 1;

    map<int, int> mapa2;
    for(int i = a + 1; i <= b; i++) {
        if(mapa2.find(vec[i]) == mapa2.end()) {
            mapa2[vec[i]] = 1;
        } else {
            mapa2[vec[i]]++;
        }
    }

    for(int i = a + 1; i <= b; i++) {
        int min_key = mapa1.begin()->first;
        int max_key = mapa2.rbegin()->first;
        if(min_key >= max_key) {
            return i;
        }
        int el = vec[i];
        if(mapa1.find(el) == mapa1.end()) {
            mapa1[el] = 1;
        } else {
            mapa1[el]++;
        }
        mapa2[el]--;
        if(mapa2[el] <= 0) mapa2.erase(el);
    }
    return -1;
}

void print_sol(vector<int> vec, int id, int k) {
    if(id == 0) {
        cout << "1 ";
        k-=2;
        int cnt = 2;
        while(k-- >= 0) {
            cout << cnt++ << " ";
        }
        return;
    }

    int cnt = 1;
    k -= 3;
    while(k-- >= 0 && cnt < id) {
        cout << cnt++ << " ";
    }
    cout << id << " ";
    cout << id + 1 << " ";
    cnt = id + 2;
    while(k-- >= 0) {
        cout << cnt++ << " ";
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> vec;
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        vec.push_back(x);
    }

    if(k == 2) {
        int res = sol_for_2(vec, 0, vec.size() - 1);
        if(res < 0) cout << "NIE" << endl;
        else {cout << "TAK" << endl;
        cout << res << endl;
        }
        return 0;
    }

    map<int, int> mapa1;
    for(int i = 0; i < vec.size(); i++) {
        if(mapa1.find(vec[i]) == mapa1.end()) {
            mapa1[vec[i]] = 1;
        } else {
            mapa1[vec[i]]++;
        }
    }

    int last = vec.size() - 1;
    int is_first = 1;



    while(1) {
        int max_key = mapa1.rbegin()->first;
        if(mapa1[max_key] == 1 && last - 1 >= 0 && vec[last] == max_key) {
            if(is_first) {
                is_first = 0;
                k--;
            } 
            last--;
            if(k == 2) {
                mapa1[max_key]--;
                if(mapa1[max_key] <= 0) mapa1.erase(max_key);
                int max_key = mapa1.rbegin()->first;
                while(mapa1[max_key] == 1 && last - 1 >= 0 && vec[last] == max_key) {
                    last--;
                    mapa1[max_key]--;
                    if(mapa1[max_key] <= 0) mapa1.erase(max_key);
                }
                int res = sol_for_2(vec, 0, last);
                if(res >= 0)  {
                    cout << "TAK" << endl;
                    cout << res << " " << last + 1 << endl;
                    return 0;
                } else {
                    cout << "NIE" << endl;
                    return 0;
                }
            }
            mapa1[max_key]--;
            if(mapa1[max_key] <= 0) mapa1.erase(max_key);
        } else {
            if(k == 2) {
                int res = sol_for_2(vec, 0, last);
                if(res < 0) cout << "NIE" << endl;
                else { cout << "TAK" << endl;
                    cout << res << endl;
                }
                return 0;
            }
            cout << "TAK" << endl;
            int id = 0;
            while(id < vec.size() && vec[id] != max_key) id++;
            print_sol(vec, id, k - 1);
            return 0;
        }
        if(last <= 0) {
            cout << "NIE" << endl;
            return 0;
        }
    }
    return 0;
}