Emily 厌倦了 2020 年整年在家学习的生活。她注意到同样的任务反复出现：她必须做饭和洗碗。然后是上课时间；之后她继续洗碗，接着去上另一门课，在最后一次做饭和洗碗之前又洗了一些碗。

不过，她的一天中有一部分是她所钟爱的：那是她当前正在进行的活动序列在一天中仅出现一次的时候。当那个活动序列既独特又非常短时，她最为高兴。

每个活动都用一个大写字母表示。给定 Emily 今天要进行的活动列表，请通过找到仅在输入中出现一次的最短子串，来帮助 Emily 找到她一天中最好的时刻。

如果做饭是 C，洗碗是 D，学习是 S，那么上述例子中的活动列表是 C D S D S D C D，而仅出现一次的最短子串是 D C。（所有的单字母子串和其他双字母子串都至少出现了两次）。

输入格式

输入包含一行，由 $N$ 个大写字母（从 ‘A’ 到 ‘Z’）组成的序列。该行以换行符结尾，换行符不被视为输入字符串的一部分。

输出格式

输出应包含一行，即输入字符串中仅出现一次的最短子串。如果存在多个最短子串（长度相同），则输出最先出现的那一个。

数据范围

• $0 < N \leqslant 300\,000$

样例

输入 1

AABAABB

输出 1

BA