시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 256 MB222100.000%

문제

Let $f(c)$ be the $0$-based alphabetic number of a small English letter $c$, hence $f(\texttt{a}) = 0$, $f(\texttt{b}) = 1$, $\ldots$, $f(\texttt{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, $\texttt{abc} \times \texttt{de} = \texttt{defefg}$, $\texttt{de} \times \texttt{abc} = \texttt{deeffg}$, $\texttt{xy} \times \texttt{yz} = \texttt{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.

예제 입력 1

ddbb

예제 출력 1

aa db

예제 입력 2

eefbbcccdddeaabaab

예제 출력 2

aab ebcdaa