Недавно в поле зрения Лёши попала одна занимательная строка \(s\), состоящая из маленьких латинских букв. Лёша сразу же разработал уникальный алгоритм с этой строкой и поспешил поделиться им с вами. Суть алгоритма заключалась в следующем.
Лёша выбирал любое количество пар символов на позициях \((i, i + 1)\) так, чтобы выполнялись следующие условия:
- для любой пары \((i, i + 1)\) выполняется \(0 \le i < |s| - 1\);
- для любой пары \((i, i + 1)\) выполняется \(s_i = s_{i + 1}\);
- не существует индекса, который находится в нескольких парах одновременно.
Далее Лёша удалял все символы строки по индексам, содержащимся в выбранных парах, и завершал алгоритм.
Теперь Лёшу интересует, какую лексикографически минимальную строку можно получить после выполнения алгоритма на каждом суффиксе заданной строки.
Выходные данные
В \(|s|\) строках выведите длины искомых строк и сами искомые строки для всех суффиксов, начиная с наибольшего по длине. Вывод может получится слишком большим, и поэтому, если длина ответа больше \(10\) символов, то вместо самого ответа выведите только первые \(5\) символов, далее «...», и далее последние \(2\) символа ответа.
Примечание
Рассмотрим первый пример.
- Наибольший по длине суффикс — вся строка «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»
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abcdd
|
3 abc
2 bc
1 c
0
1 d
|
|
2
|
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
|