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
//Author: Łukasz Pasek
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;


int main()
{
    ios_base::sync_with_stdio(0);
    int n,k;
    cin >> n >>k;
    //cout<<n<<" "<<k<<endl;
    vector<int> T(n);
    for(auto &i : T) {cin>>i;}//cout<<i<<" ";}
    //cout<<endl;
    int M=-1e9;
    int I=0;
    stack<int> A;
    queue<int> H;
    for(int i=0 ; i<n ; i++)
    {
        if(T[i]>M)
        {
            M=T[i];
            I=i;
            A.push(i);
        }
    }
    int N=n-1;
    bool help=false;
    while(!A.empty() && A.top()==N)
    {
        help=true;
        //cout<<"A.top"<<A.top()<<" "<<N<<endl;
        H.push(A.top());
        A.pop();
        if(!A.empty())I=A.top();
        N--;
    }
    if(help) k--;
    if(A.empty() && k>0) {cout<<"NIE\n";return 0;}
    int helper=0;
    if(A.top()>0) helper++;
    if(A.top()<N) helper++;
    //cout<<helper<<endl;
    //cout<<k<<endl;
    if(k>helper)
    {
        cout<<"TAK\n";
        int I=A.top();
        stack<int> output;
        int i=N-1;
        //cout<<"k "<<k<<endl;
        //cout<<"N "<<N<<endl;
        //<<"I "<<I<<endl;
        while(k>N+1)
        {
            //cout<<"H.front "<<H.front()<<endl;
            output.push(H.front());
            if(H.front()!=n-1) k--;
            H.pop();
        }
        k--; //I-ty musimy wrzucic
        if(I<N) 
        {
            output.push(N);
            k--;
        }
        if(I>0) 
        {
            k--;
        }
         for(; i>I && k>0 ; i--)
        {
            output.push(i);
            k--;
        }
        output.push(I);
        if(I>0) output.push(I-1);
        for(i=I-2; i>=0&& k>0 ; i--)
        {
            output.push(i);
            k--;
        }
       
        while(!output.empty())
        {
           if((output.top()+1)!=n) cout<<output.top()+1<<" ";
            output.pop();
        }
    }
    else if(k==2)
    {
        int a=1e9,b=-1e9;
        int i=0;
        //cout<<"I "<<I<<endl;
       // cout<<"N "<<N<<endl;
        stack<pair<int,int>> Min;
        queue<pair<int,int>> Max;
        for(i=0; i<=N ; i++)
        {
            if(a>T[i])
            {
            a=T[i];
            Min.push({a,i});
            }
        } 
        for(i=N; i>=0 ; i--)    
        {
            if(b<T[i])
            {
            b=T[i];
            }
            Max.push({b,i});
        }
       //cout<<a<<" "<<b<<endl;
       //cout<<"Max"<<Max.front().first<<" "<<Min.top().first<<endl;
       while(!Min.empty() && !Max.empty() && Max.front().first>Min.top().first)
       {
        //cout<<"Max"<<Max.front().first<<" "<<Min.top().first<<endl;
            int i=Min.top().second;
            Min.pop();
            while(!Max.empty() && Max.front().second>i) Max.pop();
       }
        //cout<<a<<" "<<b<<endl;
        if(!Min.empty() && !Max.empty() && Max.front().first<=Min.top().first) 
        {
            cout<<"TAK\n"<<Max.front().second;
            if(!H.empty()) cout<<" ";
            while(!H.empty())
            {
                cout<<H.front()<<" ";
                H.pop();
            }
        }
        else cout<<"NIE\n";
    }
    else cout<<"NIE\n";
    return 0;
}