题目描述
有一个小写英文字符串 $s$，将这个字符串复制一份，再与原字符串拼接，将会得到 $s\cdot s$，接下来，将这个双倍字符串的某个位置插入某个小写英文字母，最后得到一个字符串 $t$。
给定 $t$，请找出它对应的 $s$，若这样的 $s$ 有多种可能，则输出 $s$ 的全部可能。
输入
单个字符串 $t$，保证都是小写英文字母，且 $t$ 的长度为奇数。
输出
+ 如果不存在，输出 `No solution`；
+ 如果只存在一种可能，输出该字符串；
+ 如果存在多种可能，优先输出字典序靠前的字符串，将这些字符串用换行符隔开。
样例输入输出
提示
设 $n$ 为字符串 $t$ 的长度，
+ 对于$30\%$的数据，$n\leq 21$；
+ 对于$60\%$的数据，$n\leq 5001$；
+ 对于$100\%$的数据，$3\leq n\leq 5000001$。