Chameleon Substring

Time limit2sMemory limit512 MB

Summary

Given a string S, find the longest substring that is both a prefix and a suffix of S and also appears somewhere strictly inside S.

Level: Medium7 of 10
Topics: String matching, String, Prefix sum
Solved: No attempts yet

Problem

A substring $T$ of a string $S$ is a chameleon substring when all three conditions hold.

$T$ is a prefix of $S$ .
$T$ is a suffix of $S$ .
$T$ also occurs in $S$ at a place that is neither of those two. That is, at least one occurrence of $T$ neither starts at the first character of $S$ nor ends at the last character of $S$ .

The three occurrences may overlap.

For example, if $S =$ fixprefixsuffix, then fix is a chameleon substring. It is a prefix of $S$ , it is a suffix of $S$ , and it also occurs starting at the 7th character.

Given $S$ , find the longest chameleon substring.

Input

The first line contains the string $S$ . It consists of lowercase English letters only, and its length is between $1$ and $10^6$ .

Output

Print the longest chameleon substring on the first line. A chameleon substring is a prefix of $S$ , so its length fixes the string itself and the answer is unique. If no chameleon substring exists, print -1.

Examples7

Example 1
Input
```
fixprefixsuffix
```
Expected output
```
fix
```
Example 2
Input
```
abcdabc
```
Expected output
```
-1
```
Example 3
Input
```
qwertyqwertyqwerty
```
Expected output
```
qwerty
```
Example 4
Input
```
papapapap
```
Expected output
```
papap
```
Example 5
Input
```
a
```
Expected output
```
-1
```
Example 6
Input
```
aa
```
Expected output
```
-1
```
Example 7
Input
```
aaa
```
Expected output
```
a
```