Encrypted Palindromic Substrings

You are given an encrypted string s consisting only of lowercase English letters. Initially, the string is encrypted as follows: the first character remains unchanged, but every subsequent character is encrypted using the answer from the previous position.

More specifically, let the answer at position i (0-indexed) be denoted by k (i.e. the number of palindromic substrings that end at that position). Then, if the encrypted character at position i+1 has ASCII code c, its decrypted value is computed as:

\( \text{decrypted}_{i+1} = \left( (c-97) + k \right) \bmod 26 + 97 \)

After decrypting the string character by character and updating using the previous answer, your task is to compute for every position the number of palindromic substrings that end at that position (in the decrypted string). A substring is considered palindromic if it reads the same forwards and backwards.

Note: The decryption and palindrome counting process is done sequentially. For position 0, the decrypted character is the same as the input, and the only palindromic substring is the character itself.

inputFormat

The input consists of a single line containing the encrypted string s (a sequence of lowercase English letters).

outputFormat

Output a sequence of numbers separated by spaces. The i-th number represents the count of palindromic substrings ending at position i (0-indexed) in the fully decrypted string.

sample

aba

1 1 1