Powers of words P83564

Let $t$ be a string and $k$ be a natural number. We define $t^k$ as the result of concatening $t$ exactly $k$ times. For instance, the third power of “abbc” is “abbcabbcabbc”.

Given a string $s$, rearrange its letters so that the result is the $k$-th power of some string $t$, where $k \ge 2$.

Input

Input consists of several strings, each with between 2 and $10^5$ lowercase letters.

Output

For each given string, print a way to rearrange its letters so that the result is $t^k$, for some string $t$ and some $k \ge 2$. If there is more than one solution, choose the alphabetically largest. If there is no solution, print “NO”.