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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <bits/stdc++.h>
// #define MULTIPLE_TESTS
// #define ENDLESS_TESTS
#define TIME_LIMIT 2
// #define MEMORY_LIMIT 512

// #define ONLY_YES

using namespace std;

// Cases:
// (1) k = 2  [ab]
//     Single separation point.
//     Lowest in [A] must be >= than highest in [B].
// (2) k = 3  [ab]c
//     For any [B] that works, we can reduce it to its first element.
//     Highest in [A] >= value of [B].
// (-) k = 3  a[bc]
//     Same as (2).
// (3) k = 3  [a]b[c]
//     For any [A] that works, we can reduce it to its first element.
//     For any [C] that works, we can reduce it to its last element.
//     Maybe this is never needed?
// (4) k >= 4
//     For any sequence:
//      a) it is strictly increasing, so no partition will be a solution.
//      b) it is not strictly increasing, so it has two neighbouring elements are not strictly increasing.
//         These two elements can always be turned into regions with k >= 4.


auto compute_low(const vector<int> &data)
{
    const int n = data.size();
    vector<int> low(n);
    
    low[0] = data[0];

    for(int i = 1; i < n; ++i)
    {
        low[i] = std::min(low[i-1], data[i]);
    }

    return low;
}

auto compute_high(const vector<int> &data)
{
    const int n = data.size();
    vector<int> high(n);
    
    high[n-1] = data[n-1];

    for(int i = n-2; i >= 0; --i)
    {
        high[i] = std::max(high[i+1], data[i]);
    }

    return high;
}

void no()
{
    cout << "NIE\n";
}

template<typename ...T>
void yes(T ...vals)
{
    cout << "TAK\n";
#ifndef ONLY_YES
    ((cout << vals+1 << ' '), ...);
    cout << '\n';
#endif
}


void solve2(const vector<int> &data)
{
    const int n = data.size();
    const auto high = compute_high(data);
    const auto low = compute_low(data);
    
    for (int mid = 1; mid < n; ++mid)
    {
        // Case (1)
        if (low[mid-1] >= high[mid])
        {
            return yes(mid-1);
        }
    }

    no();
}

void solve3(const vector<int> &data)
{
    const int n = data.size();
    const auto high = compute_high(data);
    const auto low = compute_low(data);

    // Case (3)
    if (data[0] >= data[n-1])
    {
        return yes(0, n-2);
    }
    
    for (int mid = 1; mid < n-1; ++mid)
    {
        // Case (2) [ab]c
        if (low[mid-1] >= data[mid])
        {
            return yes(mid-1, mid);
        }

        // Case (2) a[bc]
        if (data[mid] >= high[mid+1])
        {
            return yes(mid-1, mid);
        }
    }

    no();
}

void solve4(const vector<int> &data, const int k)
{
    const int n = data.size();

    for (int first = 0; first < n-1; ++first)
    {
        if (data[first] >= data[first+1])
        {
            cout << "TAK\n";
#ifndef ONLY_YES
            const int print_first = std::max(0, first - (k-3) - (first == n-2 ? 1 : 0));
            const int print_last = print_first + k - 1;
            for (int i = print_first; i < print_last; ++i)
            {
                cout << i+1 << ' ';
            }
            cout << '\n';
#endif
            return;
        }
    }

    no();
}

void test()
{
    int n, k;
    cin >> n >> k;

    vector<int> data(n);
    for (auto &v : data)
    {
        cin >> v;
    }

    switch(k)
    {
        case 2: return solve2(data);
        case 3: return solve3(data);
        default: return solve4(data, k);
    }
}


int main()
{
#ifndef CONTEST_WORKSPACE
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
#endif

#ifdef ENDLESS_TESTS
    while(!(cin >> std::ws).eof())
        test();
#else
    int T = 0;

#ifdef MULTIPLE_TESTS
    cin >> T;
#else
    T = 1;
#endif

    while (T --> 0)
        test();
#endif

    return 0;
}