Four letters P70943

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 \le \mid s \mid \le 10^5$.

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”.