Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Palindromic characteristics

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPalindromic characteristics of string *s* with length |*s*| is a sequence of |*s*| integers, where *k*-th number is the total number of non-empty substrings of *s* which are *k*-palindromes.

A string is 1-palindrome if and only if it reads the same backward as forward.

A string is *k*-palindrome (*k* > 1) if and only if:

- Its left half equals to its right half.
- Its left and right halfs are non-empty (
*k*- 1)-palindromes.

The left half of string *t* is its prefix of length ⌊|*t*| / 2⌋, and right half — the suffix of the same length. ⌊|*t*| / 2⌋ denotes the length of string *t* divided by 2, rounded down.

Note that each substring is counted as many times as it appears in the string. For example, in the string "aaa" the substring "a" appears 3 times.

Input

The first line contains the string *s* (1 ≤ |*s*| ≤ 5000) consisting of lowercase English letters.

Output

Print |*s*| integers — palindromic characteristics of string *s*.

Examples

Input

abba

Output

6 1 0 0

Input

abacaba

Output

12 4 1 0 0 0 0

Note

In the first example 1-palindromes are substring «a», «b», «b», «a», «bb», «abba», the substring «bb» is 2-palindrome. There are no 3- and 4-palindromes here.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2018 02:44:37 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|