Jumps
Prapor and Kowalski enjoy jumping on ice floes. One day, they arranged a sequence of ice floes on the water, each painted in a different color. Prapor loves jumping across these ice floes, but Kowalski is quite particular — he only enjoys jumping over a segment of ice floes if, when jumping back and forth, the sequence of colors remains the same in both directions (i.e., the segment is a palindrome).
Prapor and Kowalski decided to start at a specific ice floe and jump towards the ones with increasing numbers. They began by jumping one ice floe forward and back, then two, and continued this pattern. They stopped when Kowalski no longer enjoyed jumping over the next segment of ice floes, provided there were enough ice floes to make the jump. The penguins are curious to find out the length of the first segment of ice floes that Kowalski would refuse to jump over from each starting position.
Input
The input consists of a single line of length N (1 ≤ N ≤ 10^5) representing the colors of the ice floes in order of increasing numbers. The line is composed of lowercase Latin letters, where different letters represent different colors, and identical letters represent the same color. The line ends with a newline character.
Output
Output a single line containing N non-negative integers a_i, where each integer represents the length of the first segment that Kowalski will not want to jump over starting at position i.