J. Divide The String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a string $$$s$$$ consisting of lowercase letters of the Latin alphabet.

You need to split this string into substrings according to the following requirements:

  • in each substring, the first character is equal to the last character;
  • each substring contains at least two characters;
  • each character of the string $$$s$$$ belongs to exactly one of these substrings.

Therefore, if we concatenate all the resulting substrings in the same order, we'll get the original string $$$s$$$.

A substring of the string $$$s$$$ is a non-empty sequence of consecutive letters of the string $$$s$$$.

For example, the string aadddzxxz can be split into substrings aa, ddd and zxxz.

Find the maximum number of substrings that the string $$$s$$$ can be split into, and also the sizes of each of these substrings. If the string $$$s$$$ cannot be split as described, report it.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 4 \cdot 10^5$$$) — the length of the string $$$s$$$.

The second line contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase letters of the Latin alphabet.

Output

If the string cannot be split into substrings of greater than one length that start and end with the same letter, print $$$-1$$$.

Otherwise, in the first line, print $$$k$$$ — the maximum number of substrings that the string $$$s$$$ can be split into. In the second line, print $$$k$$$ integers — the sizes of substrings that the string $$$s$$$ can be split into, in order from left to right. The sum of the output $$$k$$$ numbers must be equal to $$$n$$$.

Examples
Input
4
aaaa
Output
2
2 2
Input
15
abcbcaccbbcabca
Output
3
6 5 4
Input
4
abcd
Output
-1
Input
5
abcda
Output
1
5
Note

In the first example, the string can be split into two substrings of length two, each of which starts and ends with the letter a.

In the second example, the string can be split into three substrings abcbca, ccbbc and abca.