题目描述

有一个小写英文字符串 s，将这个字符串复制一份，再与原字符串拼接，将会得到 s⋅s，接下来，将这个双倍字符串的某个位置插入某个小写英文字母，最后得到一个字符串 t。

给定 t，请找出它对应的 s，若这样的 s 有多种可能，则输出 s 的全部可能。

输入格式

单个字符串 t，保证都是小写英文字母，且 t 的长度为奇数。

输出格式

如果不存在，输出 No solution；

如果只存在一种可能，输出该字符串；

如果存在多种可能，优先输出字典序靠前的字符串，将这些字符串用换行符隔开。

数据范围

设 n 为字符串 t 的长度，

对于30%的数据，n≤21；

对于60%的数据，n≤5001；

对于100%的数据，3≤n≤5000001。

样例数据

输入:

abcdabc

输出:

abc

输入:

abcde

输出:

No solution

输入:

ababa

输出:

ab

ba