Для каждого префикса данной строки определите, возможно ли его разбить на 1, 2, 3, 4, 5, …, n непустых палиндромов. Заметим, что если мы можем разбить строку на k палиндромов, то мы можем разбить её и на k + 2 палиндрома.
Исходные данные
Вход содержит строку из n строчных латинских букв(1 ≤ n ≤ 3 · 105).
Результат
Выведите n пар чисел.
i-я строка должна содержать минимальное нечётное k (или −1, если его не существует) и минимальное чётное k (или −2, если его не существует) такие, что мы можем разбить строку s[1..i] на k непустых палиндромов.
Пример
исходные данные | результат |
---|
abaa
| 1 -2
-1 2
1 -2
3 2
|
Замечания
abaa = aba|a = a|b|aa = a|b|a|a.
Автор задачи: Михаил Рубинчик
Источник задачи: Палиндромный контест, 11 июля 2015