Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Минлексы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно в поле зрения Лёши попала одна занимательная строка $$$s$$$, состоящая из маленьких латинских букв. Лёша сразу же разработал уникальный алгоритм с этой строкой и поспешил поделиться им с вами. Суть алгоритма заключалась в следующем.

Лёша выбирал любое количество пар символов на позициях $$$(i, i + 1)$$$ так, чтобы выполнялись следующие условия:

  • для любой пары $$$(i, i + 1)$$$ выполняется $$$0 \le i < |s| - 1$$$;
  • для любой пары $$$(i, i + 1)$$$ выполняется $$$s_i = s_{i + 1}$$$;
  • не существует индекса, который находится в нескольких парах одновременно.

Далее Лёша удалял все символы строки по индексам, содержащимся в выбранных парах, и завершал алгоритм.

Теперь Лёшу интересует, какую лексикографически минимальную строку можно получить после выполнения алгоритма на каждом суффиксе заданной строки.

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

Единственная строка ввода содержит строку $$$s$$$ ($$$1 \le |s| \le 10^5$$$) — исходную строку, состоящую из маленьких латинских букв.

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

В $$$|s|$$$ строках выведите длины искомых строк и сами искомые строки для всех суффиксов, начиная с наибольшего по длине. Вывод может получится слишком большим, и поэтому, если длина ответа больше $$$10$$$ символов, то вместо самого ответа выведите только первые $$$5$$$ символов, далее «...», и далее последние $$$2$$$ символа ответа.

Примеры
Входные данные
abcdd
Выходные данные
3 abc
2 bc
1 c
0 
1 d
Входные данные
abbcdddeaaffdfouurtytwoo
Выходные данные
18 abbcd...tw
17 bbcdd...tw
16 bcddd...tw
15 cddde...tw
14 dddea...tw
13 ddeaa...tw
12 deaad...tw
11 eaadf...tw
10 aadfortytw
9 adfortytw
8 dfortytw
9 fdfortytw
8 dfortytw
7 fortytw
6 ortytw
5 rtytw
6 urtytw
5 rtytw
4 tytw
3 ytw
2 tw
1 w
0 
1 o
Примечание

Рассмотрим первый пример.

  • Наибольший по длине суффикс — вся строка «abcdd». Выбирая одну пару $$$(4, 5)$$$, Лёша может получить строку «abc».
  • Следующий по длине суффикс — строка «bcdd». Выбирая одну пару $$$(3, 4)$$$, получаем «bc».
  • Следующий по длине суффикс — строка «cdd». Выбирая одну пару $$$(2, 3)$$$, получаем «c».
  • Следующий по длине суффикс — строка «dd». Выбирая одну пару $$$(1, 2)$$$, получаем «» (пустую строку).
  • Последний суффикс — строка «d». Нельзя выбрать ни одну пару, поэтому ответ «d».

Во втором примере для наибольшего по длине суффикса «abbcdddeaaffdfouurtytwoo» выбираем три пары $$$(11, 12)$$$, $$$(16, 17)$$$, $$$(23, 24)$$$ и получаем «abbcdddeaadfortytw»