Для каждого префикса данной строки определите, возможно ли его разбить на 1, 2, 3, 4, 5, …, n непустых палиндромов. Заметим, что если мы можем разбить строку на k палиндромов, то мы можем разбить её и на k + 2 палиндрома.

Вход содержит строку из n строчных латинских букв(1 ≤ n ≤ 3 · 10⁵).

Выведите n пар чисел. i-я строка должна содержать минимальное нечётное k (или −1, если его не существует) и минимальное чётное k (или −2, если его не существует) такие, что мы можем разбить строку s[1..i] на k непустых палиндромов.

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