images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 21:03:14

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2280. Multigram

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

C-3PO is a passionate lover of riddles. The newest type of riddles he has come across requires the solver to check whether the given word is a multigram. A multigram is a word that consists of concatenating two or more words that are all mutually anagrams. The first of these words is called the root of the multigram. For instance, the word bbabab is a multigram with the root bba because it consists of anagrams bba and bab.
Help C-3PO solve the riddle by determining whether his word is a multigram and determining its root in case it is. If there are multiple possible roots of the multigram, output the shortest.
Note: Two words are mutually anagrams if one of them can be obtained from the other by changing the letter order.
Input
The first and only line of input contains a word of length at most 300000 lowercase English characters.
Output
If the given word is not a multigram, output "No solution". Otherwise, output the shortest root of the given word in one line.

Sample Input #1

aaaa

Sample Output #1

a

Sample Input #2

ab

Sample Output #2

No solution

Sample Input #3

bbabab

Sample Output #3

bba
Clarification of the first example: Notice that the word "aa" could also be the root, but "a" is shorter.
Clarification of the second example: The word is not a multigram because "a" and "b" are not mutually anagrams.
loading