카멜레온 부분 문자열

문자열 $S$의 부분 문자열 $T$가 다음 세 조건을 모두 만족하면 $T$를 카멜레온 부분 문자열이라고 한다.

• $T$는 $S$의 접두사이다.
• $T$는 $S$의 접미사이다.
• $S$ 안에서 $T$가 위의 두 자리가 아닌 자리에도 등장한다. 즉 $S$의 첫 문자에서 시작하지도 않고 $S$의 마지막 문자에서 끝나지도 않는 $T$의 등장이 하나 이상 있다.

세 등장은 서로 겹쳐도 된다.

예를 들어 $S =$ fixprefixsuffix이면 fix는 카멜레온 부분 문자열이다. fix는 $S$의 접두사이자 접미사이고, 7번째 문자에서 시작하는 등장도 있다.

문자열 $S$가 주어지면 가장 긴 카멜레온 부분 문자열을 구한다.

첫째 줄에 문자열 $S$가 주어진다. $S$는 알파벳 소문자로만 이루어지고, 길이는 $1$ 이상 $10^6$ 이하이다.

가장 긴 카멜레온 부분 문자열을 첫째 줄에 출력한다. 카멜레온 부분 문자열은 $S$의 접두사이므로 길이가 정해지면 문자열도 하나로 정해지고, 답은 유일하다. 카멜레온 부분 문자열이 없으면 -1을 출력한다.