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
#include <iostream>
#include <bitset>
#include <vector>

using namespace std;

void case2(std::vector<int> &vec) {
    std::vector<int> suffix_max;
    int max = 0;
    for (int i=vec.size()-1; i > 0; i--) {
        max = std::max(max, vec.at(i));
        suffix_max.push_back(max);
    }
    
    int min=vec.at(0);
    for (int i=0; i < vec.size()-1; i++) {
        min = std::min(min, vec.at(i));
        if (min >= suffix_max.at(vec.size()-2-i)) {
            std::cout << "TAK\n";
            std::cout << i+1;
            return;
        }
    }
    
    std::cout << "NIE";
}

void case3(std::vector<int> &vec) {
    int min = vec.at(0);
    int max = vec.at(0);
    int min_count = 0;
    int max_count = 0;
    
    for (int i=0; i<vec.size(); i++) {
        if (vec.at(i) == max) {
            max_count++;
        } else if (vec.at(i) > max) {
            max = vec.at(i);
            max_count=1;
        }
        
        if (vec.at(i) == min) {
            min_count++;
        } else if (vec.at(i) < min) {
            min = vec.at(i);
            min_count=1;
        }
    }
    
    if (vec.at(0) == min && vec.at(vec.size()-1) == max && min_count == 1 && max_count == 1) {
        std::cout << "NIE";
        return;
    }
    
    int outsider;
    for (int i=1; i<vec.size()-1; i++) {
        if (vec.at(i) == min || vec.at(i) == max) {
            outsider = i+1;
            break;
        }
    }
    std::cout << "TAK\n";
    std::cout << outsider-1 << " " << outsider;
}

void case4OrMore(std::vector<int> &vec, int seg) {
    int prev = vec.at(0);
    std::vector<int> res;
    for (int i=1; i<vec.size(); i++) {
        if (vec.at(i) <= prev) {
            if (i != 1) {
                res.push_back(i-2);
            }
            res.push_back(i-1);
            if (i != vec.size()-1) {
                res.push_back(i);
            }
            break;
        }
        prev = vec.at(i);
    }
    if (res.size() == 0) {
        std::cout << "NIE";
        return;
    }
    
    std::cout << "TAK\n";
    int i = 0;
    while (seg > res.size() && i < res.at(0)) {
        std::cout << i+1 << " ";
        seg--;
        i++;
    }
    for (int v : res) {
        std::cout << v+1;
        seg--;
        i = v+1;
        if (seg != 0) {
            std::cout << " ";
        }
    }
    
    while (seg > 0) {
        std::cout << i+1;
        seg--;
        i++;
        if (seg != 0) {
            std::cout << " ";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int n, k;
    std::vector<int> vec;
    
    std::cin >> n >> k;
    
    for (int i=0; i<n; i++) {
        int v;
        std::cin >> v;
        vec.push_back(v);
    }
    
    std::vector<int> res;
    
    if (k == 2) {
        case2(vec);
    } else if (k == 3) {
        case3(vec);
    } else {
        case4OrMore(vec, k-1);
    }
}