For every prefix of some given string, determine whether it is possible to split it into 1, 2, 3, 4, 5, …, n nonempty 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 · 10^{5}).
Output
Output 2n integers.
The ith 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 = abaa = abaa = abaa.
Problem Author: Mikhail Rubinchik
Problem Source: Palindromic Contest, July 11, 2015