문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다.</p>

문자열 S가 주어졌을 때, 카멜레온 부분 문자열을 구하는 프로그램을 작성하시오.

예를 들어, S = "fixprefixsuffix"와 같은 경우에는 "fix"는 접두사, 접미사도 되고, 두 경우가 아닌 위치에도 등장하는 부분 문자열로도 등장한다.

입력 형식

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져있으며, 길이는 10⁶을 넘지 않는 자연수이다.

출력 형식

가능한 카멜레온 부분 문자열 T 중에서 길이가 가장 긴 것을 출력한다. 만약, T가 존재하지 않으면 -1을 출력한다.

예제 입력 1

fixprefixsuffix

예제 출력 1

fix

예제 입력 2

abcdabc

예제 출력 2

-1

예제 입력 3

qwertyqwertyqwerty

예제 출력 3

qwerty

예제 입력 4

papapapap

예제 출력 4

papap