Powers of words P83564


Statement
 

pdf   zip

thehtml

Let t be a string and k be a natural number. We define tk 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 105 lowercase letters.

Output

For each given string, print a way to rearrange its letters so that the result is tk, 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++