ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2058. 100500 palidnromes

Time limit: 1.0 second
Memory limit: 64 MB
For every prefix of some given string, determine whether it is possible to split it into 1, 2, 3, 4, 5, …, n non-empty palindromes. Note that if we can split a string into k palindromes then we can split it into k + 2 palindromes.

Input

The input contains a string of n lowercase Latin letters (1 ≤ n ≤ 3 · 105).

Output

Output 2n integers. The i-th line should contain minimal odd k (or −1 if it doesn’t exist) and minimal even k (or −2 if it doesn’t exist) such that we can split string s[1..i] into k palindromes.

Sample

inputoutput
abaa
1 -2 
-1 2 
1 -2 
3 2 

Notes

abaa = aba|a = a|b|aa = a|b|a|a.
Problem Author: Mikhail Rubinchik
Problem Source: Palindromic Contest, July 11, 2015