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

using namespace std;

int n, k;

void handle_2(vector<int> &v) {
    vector<int> suf_max(n);
    suf_max.back() = v.back();
    for (int i = n-2; i >= 0; --i)
        suf_max[i] = max(suf_max[i+1], v[i]);
    
    int pref_min = v[0];
    for (int i = 0; i < n-1; ++i) {
        pref_min = min(pref_min, v[i]);
        if (pref_min >= suf_max[i+1]) {
            cout << "TAK\n" << i+1 << '\n';
            return;
        }
    }
    cout << "NIE\n";
}

void handle_3(vector<int> &v) {
    for (int i = 1; i < n-1; ++i)
        if (v[i] <= v[0]) {
            cout << "TAK\n" << i << ' ' << i+1 << '\n';
            return;
        }

    for (int i = n-2; i > 0; --i)
        if (v[i] >= v[n-1]) {
            cout << "TAK\n" << i << ' ' << i+1 << '\n';
            return;
        }

    if (v[0] >= v[n-1]) {
        cout << "TAK\n" << 1 << ' ' << n-1 << '\n';
        return;
    }
    cout << "NIE\n";
}

int not_unique_sorted(vector<int> &v) {
    for (int i = 1; i < n; ++i)
        if (v[i] <= v[i-1])
            return i == 1 ? 2 : (i == n-1 ? n-2 : i);
    return 0;
}

void handle_geq_4(vector<int> &v) {
    int idx = not_unique_sorted(v);
    if (!idx) {
        cout << "NIE\n";
        return;
    }
    k -= 4;
    
    cout << "TAK\n";
    for (int i = 1; i < idx-1 && k > 0; ++i, --k)
        cout << i << ' ';
    cout << idx-1 << ' ' << idx << ' ' << idx+1;
    for (int i = idx+2; i < n && k > 0; ++i, --k)
        cout << ' ' << i;
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    vector<int> v(n);
    for (int &i : v)
        cin >> i;

    if (k == 2) handle_2(v);
    else if (k == 3) handle_3(v);
    else handle_geq_4(v);
}