Однажды, на уроке информатики Леше Васильеву дали придумать специальную задачу с перестановками для Дамира. Леше очень понравилась эта затея, поэтому он взял ноутбук с полки, включил и заметил, что Антон Витальевич сменил пароли. Леше известно, что пароль содержит в себе все символы лексикографически максимальной подстроки в строке S, однако у него не так много времени на перебор, задачи необходимо сдать через 40 минут!
Помогите Леше и напишите программу, которая способна вывести все варианты паролей для строки S.
Пароли выводятся в алфавитном порядке.
Подстрокой называется некоторая непустая подпоследовательность подряд идущих символов строки. Лексикографически максимальная подстрока это подстрока, стоящая на последнем месте в отсортированном по алфавиту списке всех подстрок исходной строки.
Формат входных данных
Программа получает на вход строку
S. Длина
S не более 15 символов. Строка записана строчными английскими буквами.
Формат выходных данных
Выведите в алфавитном порядке все варианты паролей для строки S. Каждый пароль выводится в отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
lesha
|
ahs
ash
has
hsa
sah
sha
|