Reorganize String

You are given a string s consisting of lowercase English letters. Your task is to rearrange the characters of s so that no two adjacent characters are the same.

If it is possible to obtain such a rearrangement, output one valid rearranged string. Otherwise, output NO.

For example, given s = "aabb", one possible valid answer is abab (another acceptable answer is baba). However, for s = "aaab", no valid rearrangement exists so the answer is NO.

Note: The solution uses a greedy approach with a heap. In cases of ties in frequency, the lexicographically smaller character is chosen first. In mathematical terms, if the count of a character is represented by f(c), the algorithm always selects the character c maximizing f(c) (with ties broken by the character’s order, i.e. using the ordering c_1 < c_2 if f(c_1) = f(c_2)).

All formulas in this description follow the LaTeX format. For example, the condition that the resulting string r must satisfy can be written as:

$$\forall i\ (1 \le i < |r|),\quad r_i \neq r_{i+1}. $$

inputFormat

The input consists of a single line containing a non-empty string s composed of lowercase English letters.

Input Format (stdin):

outputFormat

Output a single line: the rearranged string such that no two adjacent characters are identical if such an arrangement exists; otherwise, output NO.

Output Format (stdout):

## sample

aabb

abab