本题中，我们称对一个字符串进行一遍复制为在这个字符串的末尾再加上字符串本身。比如：

字符串 "ABC" 复制一遍后的结果为 "ABCABC"，复制两遍后的结果为 "ABCABCABC"。

现在给你一个字符串 S，你需要找到一个最短的字符串（设为 T），使得字符串 S 是通过字符串 T 复制至少一遍得到的。

一行，一个字符串 S。S 仅由大写英文字母组成且长度不超过 10000 。

如果不存在题目要求的 T（即不存在任何一个字符串 T 能够复制至少一遍得到字符串 S），则输出 “So Sad!”。  

否则，输出最短的字符串 T 。

样例解释：
样例1：字符串 "BBBBBBBBBB" 可以通过字符串 "B" 复制 9 遍得到；
样例2：字符串 "ABAABAABAABA" 可以通过字符串 "ABA" 复制 3 遍得到；
样例3：字符串 "ACBCABACACBCABCA" 无法由任何字符串复制至少一遍得到。

数据规模与约定：
设 |S| 表示字符串 S 的长度，则：
对于 30% 的数据，|S| ≤ 100
对于 60% 的数据，|S| ≤ 1000
对于 100% 的数据，1 ≤ |S| ≤ 10000

 达人赛青铜组