Characterithmetic
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
acacbe \(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
acacis 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
aaaaorcccc.
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, andc.
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