给定一个字符串 str1 ,找出其中最长的神奇子串str2。

(神奇子串：即是str1的前缀又是str1的后缀，并且除了前缀和后缀的地方也要出现)

Input

一个字符串，代表str1(str1的长度小于等于$1e6$)

Output

一个字符串，代表str2（若str2不存在，请输出-1）

Samples

fixprefixsuffix

fix

abcdabc

-1