ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2058. 100500 палиндромов

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Для каждого префикса данной строки определите, возможно ли его разбить на 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