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.

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

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.

abaa = aba|a = a|b|aa = a|b|a|a.