문자열 곱

영소문자 $c$의 $0$부터 시작하는 알파벳 번호를 $f(c)$라 하자. 즉 $f(`a`) = 0$, $f(`b`) = 1$, $\ldots$, $f(`z`) = 25$이다. 두 문자열 $s = s_0 \ldots s_{n - 1}$과 $t = t_0 \ldots t_{m - 1}$의 곱 $s \times t$는 문자열 $u = u_0 \ldots u_{nm - 1}$이며, 모든 $i = 0, \ldots, n - 1$과 $j = 0, \ldots, m - 1$에 대해 $f(u_{j \cdot n + i}) = (f(s_i) + f(t_j)) \bmod 26$이다. 예를 들어 $`abc` \times `de` = `defefg`$, $`de` \times `abc` = `deeffg`$, $`xy` \times `yz` = `vwwx`$이다.

문자열 $s$가 주어진다. $a \times b = s$인 두 문자열 $a$와 $b$를 찾아라. 그러한 $a, b$가 여러 쌍이면 문자열 $a + b$ ($+$는 연결을 뜻한다)가 사전순으로 가장 작은 쌍을 찾아라. 그러한 쌍이 여전히 여러 개라면 $a$의 길이가 가장 작은 쌍을 찾아라.

입력은 한 줄이며, 영소문자로 이루어진 문자열 $s$가 주어진다 ($1 \le |s| \le 10^6$).

$a \times b = s$인 두 문자열 $a, b$를 찾을 수 없으면 $-1$을 출력한다. 그렇지 않으면 $a$와 $b$를 공백으로 구분해 출력한다. $a+b$는 가능한 모든 쌍 $(a, b)$ 중 사전순으로 가장 작아야 한다. 그러한 쌍이 여러 개면 $|a|$가 가장 작아야 한다.