Note: This is an approximate problem. There is no exact solution. You must find the most optimal solution. Please refer to the sample explanation to ensure that you understand the problem correctly.

Problem statement

You are given a string $S$ of $N$ length consisting of lowercase Latin characters ($a - z$). You are required to decompose $S$ into $K$ consecutive non-empty substrings such that every character is present in only one substring.

If substrings are $S[1], S[2], S[3],\ ... , S[K]$, then select an array $B$ that is a permutation of 1 to $K$ denoting that it is of size $K$ and include every element from 1 to $K$.

Your are required to form a new string $V = S[B[1]] + S[B[2]] +\ ...  + S[B[k]]$. 

Note: The number of palindromic substrings in $V$ is $X$ (of length greater than 1).

Your task is to maximize $X$.

Input format

• The irst line contains two space-separated integers $N$ and $K$. 
• The second line contains a string $S$ of lowercase Latin characters.

Output format

• In the first $K$ lines, print one integer denoting the end index of the $i^{th}$ substring (indexes are 1 based).
• In the next line, print $K$ space-separated integers denoting array $B$ (permutation of 1 to $K$).
• The end index of substrings should be in increasing order.

Verdict and scoring

• Your score is equal to the sum of the values of all test files. The value of each test file is equal to the value of $Z$ that you find.
• If decomposition of string $S$ is invalid or array $B$ is invalid, then you receive a wrong answer verdict.

Constraints

• $N = 1000$
• $50 \le K \le 100$
• 25% test files have at most 8 distinct characters in $S$.
• 25% test files have at most 16 distinct characters in $S$.
• 50% test files have at most 26 distinct characters in $S$.