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

using namespace std;
int n, k, a, t[500007], tdmax[1100007], tdmin[1100007], pl=1, tw[500007], ok;
pair <int,int> pom[500007];
bool w, odw[500007];
int maxsra(int gdzie, int pocz, int kon, int x, int y)
{
    if(pocz>=x && kon<=y) return tdmax[gdzie];
    if(kon<x || pocz>y) return 0;
    return max(maxsra(2*gdzie, pocz, (pocz+kon)/2, x, y), maxsra(2*gdzie+1,(pocz+kon)/2+1, kon, x, y));
}
int minsra(int gdzie, int pocz, int kon, int x, int y)
{
    if(pocz>=x && kon<=y) return tdmin[gdzie];
    if(kon<x || pocz>y) return 1000000007;
    return min(minsra(2*gdzie, pocz, (pocz+kon)/2, x, y), minsra(2*gdzie+1,(pocz+kon)/2+1, kon, x, y));
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    while(pl<n) pl*=2;
    for(int i=1;i<pl*2+1;i++)
    {
        tdmin[i]=1000000007;
    }
    for(int i=0;i<n;i++)
    {
        cin>>t[i];
        tdmax[pl+i]=t[i];
        tdmin[pl+i]=t[i];
    }
    for(int i=pl-1;i>0;i--)
    {
        tdmax[i]=max(tdmax[i*2], tdmax[i*2+1]);
        tdmin[i]=min(tdmin[i*2], tdmin[i*2+1]);
    }
    if(k==2)
    {
        for(int i=0;i<n-1;i++)
        {
            if(minsra(1, pl, 2*pl-1, pl, i+pl)>=maxsra(1, pl, 2*pl-1, i+pl+1, n+pl))
            {
                w=1;
                tw[0]=i+1;
                break;
            }
        }
        if(w)
        {
            cout<<"TAK\n"<<tw[0];
        }
        else cout<<"NIE";
    }
    else if(k==3)
    {
        if(t[0]>=t[1]) {cout<<"TAK\n1 2"; return 0;}
        if(t[n-2]>=t[n-1]) {cout<<"TAK\n"<<n-2<<" "<<n-1; return 0;}
        for(int i=1;i<n-1;i++)
        {
            if(t[i]<=minsra(1, pl, 2*pl-1, pl, i+pl-1) || t[i]>=maxsra(1, pl, 2*pl-1, i+pl+1, n+pl))
            {
                cout<<"TAK\n"<<i<<" "<<i+1;
                return 0;
            }
        }
        cout<<"NIE";
    }
    else
    {
        for(int i=0;i<n-1;i++)
        {
            if(t[i]>=t[i+1])
            {
                w=1;
                tw[0]=i+1;
                tw[1]=i+2;
                odw[i]=1;
                odw[i+1]=1;
                k-=3;
                ok=2;
                if(i>0) {tw[2]=i; ok++; k--; odw[i-1]=1;}
                break;
            }
        }
        if(w)
        {
            for(int i=0;i<n && k>0;i++)
            {
                if(!odw[i])
                {
                    tw[ok]=i+1;
                    ok++;
                    k--;
                }
            }
            sort(tw, tw+ok);
            cout<<"TAK\n";
            for(int i=0;i<ok;i++)
            {
                cout<<tw[i]<<" ";
            }
        }
        else cout<<"NIE";
    }
    return 0;
}