令 $f(c)$ 为小写英文字母 $c$ 在字母表中的 0-基索引，即 $f(\text{a}) = 0, f(\text{b}) = 1, \dots, f(\text{z}) = 25$。 两个字符串 $s = s_0 \dots s_{n-1}$ 和 $t = t_0 \dots t_{m-1}$ 的积 $s \times t$ 是一个字符串 $u = u_0 \dots u_{nm-1}$，其中对于所有 $i = 0, \dots, n-1$ 和 $j = 0, \dots, m-1$，满足 $f(u_{j \cdot n + i}) = (f(s_i) + f(t_j)) \pmod{26}$。例如，$\text{abc} \times \text{de} = \text{defefg}$，$\text{de} \times \text{abc} = \text{deeffg}$，$\text{xy} \times \text{yz} = \text{vwwx}$。

给定一个字符串 $s$。请找到两个字符串 $a$ 和 $b$，使得 $a \times b = s$。如果存在多种 $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|$ 应尽可能小。

样例

样例输入 1

ddbb

样例输出 1

aa db

样例输入 2

eefbbcccdddeaabaab

样例输出 2

aab ebcdaa