Description

小金在研究字符串，他发现很多字符串似乎有隐藏密码，于是他找到了一种从给定字符串中解读隐藏密码的方法，隐藏密码满足一下条件： 1）隐藏密码是给定字符串的前缀 2）隐藏密码是给定字符串的后缀 3）隐藏密码是给定字符串中的某一部分，即s中非前缀和后缀的一个子串； 现给丁一个字符串s，请你找出该字符串中的隐藏密码，如果有多个请输出最长的一个，如果不存在则输出-1. 例如： 字符串s位okyookyooky，其中oky既是s的前缀，也是s的后缀，还是s中非前缀和后缀的一个子串，并且没有比它更长的满足条件的子串了，所以输出oky； 字符串s为hellohello，其中没有同时满足三个条件的字符串，所以输出-1.

Format

Input

一个只包含小写字母的字符串s。

Output

一个字符串，表示符合题目条件的隐藏密码，如果不存在则输出-1.

Samples

okyookyooky

oky

Limitation

测试点1～10: 1<=s的长度<=10⁶.