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
//Wiktor Kotala
#include <bits/stdc++.h>
#define f first
#define s second
#define add push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
const int N = 500'005;
const int inf = 2'000'000'000;
int A[N], B[N];
int minpref[N];
int maxsuf[N];
vector<int> V, odp;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,k;
    pint minEl, maxEl;
    minEl = {inf, -1};
    maxEl = {-inf, -1};

    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> A[i];
        if(A[i] <= minEl.f)
            minEl = {A[i], i};
        if(A[i] > maxEl.f)
            maxEl = {A[i], i};
    }

    if(k==2){
        minpref[0] = inf;
        maxsuf[n+1] = -inf;
        for(int i=1; i<=n; i++){
            minpref[i] = min(minpref[i-1], A[i]);
            maxsuf[n-i+1] = max(maxsuf[n-i+2], A[n-i+1]);
        }

        for(int v=1; v<n; v++){
            if(minpref[v] >= maxsuf[v+1]){
                V.add(v);
                break;
            }
        }
    }
    else if(k==3){
        if(minEl.f == maxEl.f){
            V.add(1);
            V.add(2);
        }
        else if(minEl.s != 1){
            V.add(minEl.s-1);
            V.add(minEl.s);
        }
        else if(maxEl.s != n){
            V.add(maxEl.s-1);
            V.add(maxEl.s);
        }
    }
    else{
        for(int i=1; i<=n; i++){
            B[i] = A[i];
        }
        sort(B+1, B+n+1);

        for(int i=1; i<n; i++){
            if(A[i] == A[i+1]){
                V.add(i-1);
                V.add(i);
                V.add(i+1);
                break;
            }
        }

        if(V.empty()){
            for(int i=n; i>1; i--){
                if(A[i] != B[i]){
                    V.add(i);
                    break;
                }
            }
            if(!V.empty()){
                int v = B[V.front()];
                int x;
                for(int i=V.front()-1; ; i--){
                    if(A[i] == v){
                        x = i;
                        break;
                    }
                }

                V.add(x); V.add(x-1);
            }
        }
    }

    if(V.empty()){
        cout << "NIE";
    }
    else{
        cout << "TAK\n";
        for(auto it = V.begin(); it != V.end(); ){
            if(*it <= 0 || *it >= n)
                it = V.erase(it);
            else
                it++;
        }
        odp = V;
        for(int i=1; odp.size() < k-1; i++){
            if(count(V.begin(), V.end(), i) == 0){
                odp.add(i);
            }
        }
        sort(odp.begin(), odp.end());
        for(const int& ind : odp){
            cout << ind << ' ';
        }
    }

	return 0;
}