String Product

Let $f(c)$ be the $0$-based alphabetic number of a small English letter $c$, so $f(`a`) = 0$, $f(`b`) = 1$, $\ldots$, $f(`z`) = 25$. The product $s \times t$ of two strings $s = s_0 \ldots s_{n - 1}$ and $t = t_0 \ldots t_{m - 1}$ is the string $u = u_0 \ldots u_{nm - 1}$ where $f(u_{j \cdot n + i}) = (f(s_i) + f(t_j)) \bmod 26$ for all $i = 0, \ldots, n - 1$ and $j = 0, \ldots, m - 1$. For example, $`abc` \times `de` = `defefg`$, $`de` \times `abc` = `deeffg`$, $`xy` \times `yz` = `vwwx`$.

You are given a string $s$. Find two strings $a$ and $b$ such that $a \times b = s$. If several pairs $(a, b)$ work, find the one for which the string $a + b$ ($+$ means concatenation) is lexicographically smallest. If several such pairs remain, find the one with the smallest length of $a$.

The only line of the input contains the string $s$ of small English letters ($1 \le |s| \le 10^6$).

If no two strings $a, b$ satisfy $a \times b = s$, print $-1$. Otherwise, print $a$ and $b$ separated by a space. Among all suitable pairs $(a, b)$, $a+b$ must be lexicographically smallest. If several pairs tie, $|a|$ must be smallest possible.