Note: This is an approximate problem. There is no exact solution. You must find the most optimal solution. Please, take a look at 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). Your task is to decompose $S$ into $K$ consecutive non-empty substrings such that every character is present in only one substring.

For example, substrings are $S[1], S[2], ... , S[K]$. Select an array $B$ which is a permutation of $1$ to $K$, that is, it is of size $K$ and include every element from $1$ to $K$.

Also, you can choose to keep each substring as it is or in reverse order.

Now, form a new string $V= S[B[1]] + S[B[2]] + ... + S[B[K]]$. Suppose the number of palindromic substrings in $V$ is $X$ (of length greater than 1) and the number of substrings among $S[1], S[2], ... , S[K]$ which were not reversed are $Y$.

The aim is to maximize $Z = X\times (Y + 1)$.

Input format

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

Output format

• In the first $K$ lines, print $2$ integers denoting the end index of the $i^{th}$ substring (indexes are $1$-based) and whether it is reversed or not ($0$ for not reversed and $1$ for reversed).
• 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 found.

• If the decomposition of string $S$ is invalid or array $B$ is invalid, then you will receive a wrong answer verdict.

Constraints

$N = 1000$

$50 \le K \le 100$