23644번 - String Product 다국어

문제

Let $f(c)$ be the 0ドル$-based alphabetic number of a small English letter $c,ドル hence $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 a 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 there are multiple options of $a$ and $b,ドル find the one such that the string $a + b$ (where $+$ stands for concatenation) is lexicographically smallest. If there are still several answers, 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 it is impossible to find two strings $a, b$ such that $a \times b = s,ドル print $-1$. Otherwise, print $a$ and $b$ separated by a space. The string $a+b$ should be lexicographically smallest among all suitable pairs $(a, b)$. In case of a tie, $|a|$ should be smallest possible.

제한

힌트