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 ≥ 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 ≥ 2.
If there is more than one solution, choose the alphabetically largest.
If there is no solution, print “NO”.

Public test cases

**Input**

abba xyz ww oppoop aaaaaaaaiiii

**Output**

baba NO ww popopo iiaaaaiiaaaa

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++