Characterithmetic


Submit solution

Points: 1
Time limit: 3.0s
Memory limit: 1000M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

While solving one problem after the other in your favourite programming contest (hopefully, the one you are at right now!), you are suddenly faced with an Alternative Arithmetic Problem for the Jury's Entertainment. In this problem, you are not calculating with numbers, but with strings.

For some arbitrary string \(t\) and integer \(k\), we define \(t \odot k\) (\(t\) times \(k\)) to be the string \(t\) concatenated \(k\) times. If \(t\) can be written as \(t' \odot k\) for some other string \(t'\), we say that \(k\) is a divisor of \(t\). For example, the divisors of the string abababab are \(1, 2,\) and \(4\), because this string can be written as either abababab \(\odot 1\), or abab \(\odot 2\), or ab \(\odot 4\). Finally, we say that a string is indivisible if its only divisor is \(1\): for example, the string abc is indivisible.

You are given a string \(s\) of length \(n\), that contains only the characters a, b, and c. For each divisor \(d\) of \(n\), you need to change some of the characters (to either a, b, or c), so that the largest divisor of \(s\) becomes \(d\). Find the minimum number of characters that need to be changed in order to make this true.

As an example, consider the first sample input. There are three answers, one for each of the divisors of \(4\):

  • To make the largest divisor of acac be \(1\), we need to make sure that \(2\) is not a divisor. We can change any character to make the string indivisible, e.g. bcac.
  • The largest divisor of acac is already \(2\), so no characters need to change and the answer is \(0\).
  • To make the largest divisor \(4\), we need to make all characters equal. To do this, \(2\) characters need to be changed, yielding either aaaa or cccc.

Input

The input consists of:

  • One line with an integer \(n \ (2 \le n \le 10^5)\), the length of your string.
  • One line with a string \(s\) of length \(n\), consisting only of characters a, b, and c.

Output

For each divisor \(d\) of \(n\), in increasing order, output the minimum number of characters that you need to change to make the largest divisor of \(s\) equal to \(d\).

Examples

Sample 1

input

4
acac

output

1 0 2
Sample 2

input

6
abccba

output

0 2 4 4

Comments

There are no comments at the moment.