题目描述

我们称字符串中任意个连续的字符组成的子序列称为该串的子串。

在本题中，对于一个字符串 $s$，如果 $s$ 存在至少两个非空子串（即至少包含一个字符的子串）均为 $s'$，则我们称 $s'$ 是 $s$ 的 重复非空子串 。

比如：字符串 "abcabc" 的重复子串有 "a"、"b"、"c"、"ab"、"bc"、"abc"。

现在给你一个字符串 $s$，请你求出字符串 $s$ 的最长重复非空子串；如果具有多个最长重复非空子串，输出其中字典序最小的那个。

输入格式

输入共一行，包含一个字符串 $s$。数据保证 $s$ 均有小写英文字母组成，且长度不超过 $1000$。

输出格式

输出共一行，包含一个字符串，表示 $s$ 的最长重复非空子串。如果 $s$ 存在多个最长重复非空子串，输出其中字典序最小的那个。如果 $s$ 不存在任何重复非空子串，输出 “So Sad!”。

样例

abcabc

abc

bababab

abab

abcdefg

So Sad!

样例解释

• 样例1中，"abcabc"的最长重复非空子串为 "abc"（出现了 $2 次）；
• 样例2中，"bababab" 的最长重复非空子串有 "baba" 和 "abab"，但是 "abab" 的字典序较小，所以输出了 "abab"。
• 样例3中，"abcdefg" 不存在任何出现次数超过 $2$ 次的子串，所以输出了 "So Sad!"。

数据范围

设 $|s|$ 为字符串 $s$ 的长度，则：

• 对于 $20\%$ 的数据，$|s| \le 10$；
• 对于 $60\%$ 的数据，$|s| \le 100$；
• 对于 $100\%$ 的数据，$1 \le |s| \le 1000$。

数据保证 $s$ 仅由小写英文字母构成。