M. Decomposition into Good Strings
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

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.

Examples
Input
2
abacaba
Output
-1 1 1 2 2 3 3