E. Хитрый и умный пароль
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В эпоху своей молодости герой нашего рассказа Царь Цопа решил, что все его личные данные не очень хорошо скрыты от посторонних глаз, а для монарха это недопустимо. Поэтому он придумал хитрый и умный пароль (лишь спустя много лет Цопа узнал, что его пароль — это палиндром нечетной длины), а затем зашифровал все свои данные.

Как известно, монархи в душе такие же люди, как и все остальные смертные, и поэтому чтобы не забыть свой хитрый и умный пароль, Цопа решил записать его на бумажку. Зная, что опасно хранить пароль в таком виде, он решил его зашифровать следующим образом: с конца и с начала своего пароля-палиндрома он отрезал по x символов (x может быть равно 0, и 2x строго меньше, чем длина пароля). У него получились 3 части пароля. Назовем их prefix, middle и suffix соответственно, причем prefix и suffix имеют одинаковую, возможно нулевую, длину, а middle — всегда нечётной длины. Из этих трех частей он сделал строку A + prefix + B + middle + C + suffix, где A, B и C — некоторые придуманные Цопой строки (возможно нулевой длины), а « + » означает операцию конкатенации («склеивания» строк).

Прошло много лет, и буквально вчера Царь Цопа нашел бумажку, где был записан его пароль, зашифрованный описанным выше способом. Сам пароль, а также строки A, B и C давно уже забыты, и поэтому Цопа просит вас найти пароль максимальной длины, который мог бы быть придуман, зашифрован и записан Цопой.

Входные данные

Входные данные представляют собой единственную строку из прописных латинских букв длиной от 1 до 105 символов.

Выходные данные

В первую строку выведите одно целое число k — количество непустых частей пароля в получившемся у вас ответе (). Далее выведите k строк по два целых числа xi и li — позицию начала и длину соответствующей части пароля. Пары выводите в порядке возрастания xi. Числа в паре при выводе разделяйте одним пробелом.

Позиция начала xi — целое число от 1 до длины входной строки. Никакая длина li не может быть равна 0, так как части пароля нулевой длины выводить не нужно. Среднее из чисел li обязательно должно быть нечётным.

Если решений несколько, выведите любое. Учтите, что ваша задача — максимизировать не k, а сумму li.

Примеры
Входные данные
abacaba
Выходные данные
1
1 7
Входные данные
axbya
Выходные данные
3
1 1
2 1
5 1
Входные данные
xabyczba
Выходные данные
3
2 2
4 1
7 2