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

Given a string S of N length consisting of lowercase latin characters (a - z). We need to decompose S into K consecutive non empty substrings such that every character is present in only one substring.

Say substrings are S[1], S[2], S[3], .... , S[K]. Choose a array B , which is a permutation of 1 to K i.e. it is of size K and include every element from 1 to K.

Now , form a new string V = S[B[1]] + S[B[2]] + ......  + S[B[k]]. 

Suppose, X is the length of the longest palindromic substring present in string V.

Aim is to maximize X.

Input format :

• First line contains two space-separated integers : N and K 
• Second line contain a string S, of lowercase latin characters.

Output format :

• In the first K lines, print one integer denoting end index of i-th substring (indexes are 1 based).
• In next line print K space separated integers, denoting array B (permutation of 1 to K)
• 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 X that you found.

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

Constraints :

• $N = 10^3$
• $50 \le K \le 10^2$
• 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