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 ≥ 2.

Input

Input consists of several strings, each with between 2 and 10⁵ 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”.