题目描述

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

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

输入格式

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

输出格式

• 如果不存在，输出 No solution；
• 如果只存在一种可能，输出该字符串；
• 如果存在多种可能，优先输出字典序靠前的字符串，将这些字符串用换行符隔开。

abcdabc

abc

abcde

No solution

ababa

ab
ba

数据范围

设 $n$ 为字符串 $t$ 的长度，

• 对于$30\%$的数据，$n\leq 21$；
• 对于$60\%$的数据，$n\leq 5001$；
• 对于$100\%$的数据，$3\leq n\leq 5000001$。