CSES 3138 ↗

All Palindromes

For each position, the length of the longest palindrome ending there.

0
submissions
—
best score

Given a string, calculate for each position the length of the longest palindrome that ends at that position.

Input

The only line contains a string of length n. Each character is one of a–z.

Output

Print n numbers: the length of each palindrome.

Constraints

  • 1≤n≤2⋅105

Example

Input:

ababbababaa

Output:

1 1 3 3 2 4 6 8 5 5 2

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/AllPalindromes/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.