Problem Description

This problem is translated from PA 2022 Round 2 Podwyżki.

For Bytecorp, 2022 was a tough year. Bad business decisions combined with a weak market situation mean that the company cannot afford to give employees raises. To prepare for uncomfortable questions from employees, the HR department invented a way to prove that employees do not deserve a raise.

Based on the total revenue generated by an employee over consecutive days, a year (in Byteotia, a year does not have to be 365 days) can be divided into several intervals, which will show that the employee is not working hard. More precisely, the HR department wants to split the revenue sequence into $k$ consecutive intervals, so that every element of the sequence belongs to exactly one interval. Such a split is considered correct if it is impossible to choose one element from each interval such that the chosen elements form a strictly increasing sequence.

The future of Bytecorp is in your hands. Write a program that reads the revenue sequence produced by an employee and an integer $k$, and splits the sequence into $k$ segments according to the HR department’s requirement, or decides that it is impossible to split it into such $k$ segments.

Input Format

The first line contains two integers $n, k$, denoting the length of the sequence and the number of segments to split into.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, denoting the revenue sequence.

Output Format

If the sequence cannot be split as described above, output one line with the string NIE.

Otherwise, output two lines. The first line should be the string TAK. The second line should output $k - 1$ integers $v_1, \ldots, v_{k-1}$, meaning that in a correct split, they are the right endpoints of each consecutive interval except the last one. The right endpoint of the last interval must be $n$.

If there are multiple correct answers, you may output any one of them.

6 3
3 5 4 8 3 7

TAK
3 5

4 2
2 3 2 3

NIE

Hint

For $100\%$ of the testdata, it holds that:

$2 \le k \le n \le 5 \times 10 ^ 5, 1 \le a_i \le 10^9, 1 \le v_i < n, v_i < v_{i+1}$。

Translated by ChatGPT 5