Four letters P70943


Statement
 

pdf   zip

thehtml

You are given a string with only lowercase letters between ‘a’ and ‘d’. Arrange the letters in any way so that the result is the smallest possible according to the lexicographical order. The only restriction is that the ASCII codes of any two adjacent letters in the string must differ in at least 2.

Input

Input consists of several strings with only letters chosen among ‘a’, ‘b’, ‘c’ and ‘d’. You can assume 1 ≤ ∣ s ∣ ≤ 105.

Output

For every string, print the alphabetically smallest permutation of its letters that fulfils the restriction given above. If there is no solution, print “NO”.

Public test cases
  • Input

    a
    ba
    ddbb
    abbcdd
    aaabbccddd
    

    Output

    a
    NO
    bdbd
    bdbdac
    acacadbdbd
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++