Today while studying Omar reads many words in books and references. He feels bored enough to stop reading he has noticed something strange. All the words in some statement can be read the same from left to right and from right to left. Later, Omar discovered that this type of strings is called palindromic strings.

After some thinking Omar wants to create a new type of strings and gives that type a name derived from his name, so he invents a new type of strings and calls it omeric strings. Omar's friend Hazem loves prefixes and Eid loves suffixes so Omar will take this into consideration while inventing the new type. To make a string omeric from a string s you should concatenate the longest palindromic suffix with the longest palindromic prefix.

Then Omar wants to know how many times each prefix of his omeric string can be found in this string as a substring. Substring of the string can be defined by two indices L and R and equals \(s_L s_{L+1} \dots s_R\).

Input:

The first line of the input contains a string s of length N, \(1 \le N \le 10 ^ 5\).
The given string consists only of lowercase characters.

Output:

Print the omeric string in the first line. Print the frequency of each prefix in the second line.