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
// Author: Bartek Knapik
#include <cstdio>

int n, k;
int a[500009];
int pre_min[500009];
int post_max[500009];

inline int check()
{
    for (int i = 1; i < n; ++i)
    if (a[i] <= a[i - 1])
        return i;
    return -1;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);

    int drop = check();

    if (drop == -1)
        printf("NIE\n");
    else
    {
        if (k == 2)
        {
            pre_min[1] = a[0];
            post_max[n - 1] = a[n - 1];
            for (int i = 1; i < n; ++i)
                pre_min[i + 1] = a[i] < pre_min[i] ? a[i] : pre_min[i];
            for (int i = n - 1; i > 0; --i)
                post_max[i - 1] = a[i - 1] > post_max[i] ? a[i - 1] : post_max[i];
            int ans = -1;
            for (int i = 1; i < n; ++i)
            if (pre_min[i] >= post_max[i])
            {
                ans = i;
                break;
            }
            if (ans != -1)
                printf("TAK\n%d\n", ans);
            else
                printf("NIE\n");
        }
        else if (k == 3)
        {
            int i0;
            for (i0 = 1; i0 < n && a[0] < a[i0]; ++i0);
            int i1;
            for (i1 = n - 2; i1 >= 0 && a[i1] < a[n - 1]; --i1);
            if (i0 < n - 1)
                printf("TAK\n%d %d\n", i0, i0 + 1);
            else if (i1 >= 0)
                printf("TAK\n%d %d\n", i1, i1 + 1);
            else printf("NIE\n");

        }
        else
        {
            printf("TAK\n");
            if (drop == n - 1)
            {
                for (int i = 1; i <= k - 3; ++i)
                    printf("%d ", i);
                printf("%d %d\n", drop - 1, drop);
            }
            else if (drop == 1)
            {
                int to_print = k - 3;
                printf("%d %d ", drop, drop + 1);
                for (int i = drop + 2; to_print; ++i)
                {
                    to_print--;
                    printf("%d ", i);
                }
                printf("\n");
            }
            else
            {
                int to_print = k - 4;
                for (int i = 1; to_print && i < drop - 1; ++i)
                {
                    to_print--;
                    printf("%d ", i);
                }
                printf("%d %d %d ", drop - 1, drop, drop + 1);
                for (int i = drop + 2; to_print; ++i)
                {
                    to_print--;
                    printf("%d ", i);
                }
                printf("\n");
            }
        }
    }
    return 0;
}