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
input | output |
---|
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