ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Later is better than never

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Dynamic string complexity

Time limit: 2.0 second
Memory limit: 64 MB
A substring of a string S is a contiguous sequence of characters within S. The prefix of a string S is a substring that includes the first character of S. The suffix of a string S is a substring that includes the last character of S.
Consider the string “qualification”. The strings “fat” or “lion” are not its substrings, because the characters of these strings do not go in it one after another. “cat” and “alif” are substrings but they both are neither a prefix nor a suffix. “qual” is a prefix and “cation” is a suffix. The string “qualification” is both a prefix and a suffix of itself.
In this problem the characters in strings are indexed from zero.
A period of a string S is the minimum positive integer T such that for any 0 ≤ i < |S| it is true that S[i] = S[i mod T], where i mod T is the remainder of the division of i by T.
A border of a string S is a non-empty prefix that is not equal to string S and equal to its suffix. A complexity of a string is the number of different periods of its borders. A dynamic complexity of a string is the sum of complexities of all its prefixes.
For a given binary string S and for each integer i from 1 to 25 you should find a binary string of length |S| + i, where the string S is a prefix, such that its dynamic complexity is the maximal possible.

Input

The single line contains a binary string S, 0 ≤ |S| ≤ 105, that consists only of characters {X, .}.

Output

For each i from 1 to 25 you have to output the maximal dynamic complexity of a string S + T, where |T| = i.

Sample

inputoutput
X.X
2
4
5
7
9
12
14
16
19
21
23
26
30
32
35
38
41
45
47
50
54
58
62
67
70
Problem Author: Alexey Kotelnikov, idea by Mikhail Rubinchik, special thanks to Vladislav Isenbaev
To submit the solution for this problem go to the Problem set: 2137. Dynamic string complexity