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
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <set>
using namespace std;

const int MAXN = 500000;
int n, k;
int a[MAXN];


void do_case_2() {
    multiset<int> left, right;
    
    left.insert(a[0]);
    for(int i = 1; i < n; i++)
        right.insert(a[i]);
    
    for(int i = 1; i < n; i++) {
        if( *(left.begin()) >= *(right.rbegin()) ) {
            cout << "TAK" << endl << i << endl;
            return;
        }
        left.insert(a[i]);
        right.erase(right.find(a[i]));
    }
    cout << "NIE" << endl;
}


void do_case_3() {
    for(int i = 1; i < n-1; i++) {
        if(a[0] >= a[i]) {
            cout << "TAK" << endl << i << " " << i+1 << endl;
            return;
        }
    }
    
    for(int i = n-2; i>0; i--) {
        if(a[n-1] <= a[i]) {
            cout << "TAK" << endl << i << " " << i+1 << endl;
            return;
        }
    }
    
    cout << "NIE" << endl;
    
}

void do_case_many() {
    for(int i = 1; i < n; i++) {
        if(a[i-1] >= a[i]) {
            set<int> breaks;
            if(i > 1)
                breaks.insert(i-1);
            breaks.insert(i);
            if(i+1 < n)
                breaks.insert(i+1);
            for(int j = 1; breaks.size()<k-1; j++)
                breaks.insert(j);
            cout << "TAK" << endl;
            for(auto it = breaks.begin(); it!= breaks.end(); it++)
                cout << *it << " ";
            cout << endl;
            return;
        }
    }
    cout << "NIE" << endl;
}


int main()
{
    cin >> n >> k;
    for(int i=0; i < n; i++)
        cin >> a[i];
    
    if(k==2) 
        do_case_2();
    else if(k==3)
        do_case_3();
    else 
        do_case_many();
    

    return 0;
}