403032: GYM100971 M Decomposition into Good Strings

Sometimes, in string problems you have to find a string satisfying some conditions. The authors again were too lazy to think of a tricky term for such string, so they called it good.

A string is called good if it contains exactly k different characters. You are given a string s. Find the minimal number of good strings so that their concatenation is s.

The first line contains an integer k (1 ≤ k ≤ 26).

The second line contains a string s (1 ≤ |s| ≤ 200000), consisting of lowercase Latin letters.

For every prefix of s, starting from the prefix consisting of the first character of s, and ending with s itself, output the minimal number of good strings so that their concatenation is this prefix. Solutions will be tested more carefully this way, won't they?

If for some prefix the decomposition into good strings isn't possible, output «-1» for it.

2
abacaba

-1 1 1 2 2 3 3