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
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
constexpr int LIM = 5e5;
int tab[LIM + 10];
int mx[LIM + 10];
int mn[LIM + 10];
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &tab[i]);
    }
    mn[0] = 1e9;
    for(int i = 1; i <= n; i++) {
        mn[i] = min(mn[i - 1], tab[i]);
    }
    for(int i = n; i >= 1; i--) {
        mx[i] = max(mx[i + 1], tab[i]);
    }
    bool czy = 1;
    for(int j = 2; j <= n; j++) {
        if(tab[j] <= tab[j - 1]) {
            czy = 0;
        }
    }
    if(czy) {
        printf("NIE\n");
        return 0;
    }
    if(k == 2) {
        for(int i = 1; i < n; i++) {
            if(mn[i] >= mx[i + 1]) {
                printf("TAK\n");
                printf("%d\n", i);
                return 0;
            }
        }
        printf("NIE\n");
    }   
    else if(k == 3) {
        pair<int, int>mn2 = {1e9, 0};
        for(int i = 1; i <= n; i++) {
            if(mn2.st >= tab[i]) {
                mn2.st = tab[i];
                mn2.nd = i;
            }
        }
        if(mn2.nd != 1) {
            printf("TAK\n");
            if(mn2.nd < n) {
                printf("%d %d\n", mn2.nd - 1, mn2.nd);
            }
            else {
                printf("%d %d\n", 1, mn2.nd - 1);
            }
            return 0;
        }
        pair<int, int>mx2 = {-1e9, n + 1};
        for(int i = n; i >= 1; i--) {
            if(mx2.st <= tab[i]) {
                mx2.st = tab[i];
                mx2.nd = i;
            }
        }
        if(mx2.nd != n) {
            printf("TAK\n");
            if(mx2.nd == 1) {
                printf("%d %d\n", mx2.nd, n - 1);
            }
            else {
                printf("%d %d\n", mx2.nd - 1, mx2.nd);
            }
            return 0;
        }
        printf("NIE\n");
        return 0;
    }
    else {
        printf("TAK\n");
        set<int>s;
        for(int i = 2; i <= n; i++) {
            if(tab[i] <= tab[i - 1]) {
                if(i - 2) {
                    s.insert(i - 2);
                }
                s.insert(i - 1);
                if(i < n) {
                    s.insert(i);
                }
                break;
            }
        }
        for(int i = 1; i < n; i++) {
            if(s.size() < k - 1) {
                s.insert(i);
            }
        }
        for(auto x : s) {
            printf("%d ", x);
        }
    }
}