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
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
#include <unordered_set>
#include <set>
#include <queue>
#include <utility>
#include <algorithm>
#include <cassert>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
typedef vector<ll> vi;


const int S = 1e6 + 7;
const int mod = 1e9 + 7;
int tab[S], n, m, k, pref[S], suf[S];

// inject here

bool is_strictly_increasing(){
    for (int i = 1; i < n; i ++){
        if (! (tab[i] < tab[i + 1])){
            return false;
        }
    }
    return true;
}

void check_for_k3(int pos){
    if (pref[pos - 1] < tab[pos] && tab[pos] < suf[pos + 1]) 
        return;
    cout << "TAK\n";
    cout << pos - 1 << " " << pos << endl;
    exit(0);
}

void solve(){
    cin >> n >> k;
    for (int i = 1; i <= n; i ++){
        cin >> tab[i];
    }

    if (is_strictly_increasing()){
        cout << "NIE\n";
        return;
    } else if (k >= 4){
        cout << "TAK\n";
        for (int i = 2; i <= n; i ++){
            if (tab[i - 1] >= tab[i]){
                vector<int> mid_to_left = {1, i - 2};
                vector<int> mid_to_right = {1, n - i};

                if (mid_to_left.back() == 0) mid_to_left.pop_back();
                if (mid_to_right.back() == 0) mid_to_right.pop_back();
                
                while (mid_to_left.size() + mid_to_right.size() < k){
                    if (mid_to_left.back() > 1){
                        int buffer = mid_to_left.back();
                        mid_to_left.back() = 1;
                        mid_to_left.push_back(buffer - 1);
                    } else if (mid_to_right.back() > 1){
                        int buffer = mid_to_right.back();
                        mid_to_right.back() = 1;
                        mid_to_right.push_back(buffer - 1);
                    }
                }
                reverse(mid_to_left.begin(), mid_to_left.end());
                for (auto e : mid_to_right){
                    mid_to_left.push_back(e);
                }
                auto X = mid_to_left;
                int sum = 0;
                for (int i = 0; i < (int) X.size() - 1; i ++){
                    sum += X[i];
                    cout << sum << " ";
                }
                cout << endl;
                return;
            }
        }
    } else {
        pref[0] = mod;
        suf[n + 1] = 0;
        for (int i = 1; i <= n; i ++){
            pref[i] = min(pref[i - 1], tab[i]);
        }
        for (int i = n; i >= 1; i --){
            suf[i] = max(suf[i + 1], tab[i]);
        }
        if (k == 2){
            for (int i = 2; i <= n; i ++){
                if (pref[i - 1] >= suf[i]){
                    cout << "TAK\n";
                    cout << i - 1 << "\n";
                    return;
                }
            }
        } else {
            pi min_p = {tab[2], 2}, max_p = {tab[2], 2};
            for (int i = 3; i < n; i ++){
                min_p = min(min_p, {tab[i], i});
                max_p = max(max_p, {tab[i], i});
            }
          //  cout << min_p.first << " " << min_p.second << endl;
            check_for_k3(min_p.second);
            check_for_k3(max_p.second);
        }
        cout << "NIE\n";
    }
}


int main(){
    ios_base::sync_with_stdio(0);
    int t = 1;
   //cin >> t;
    while (t --)
        solve();

    return 0;
}