Rearrange Characters to Avoid Adjacent Duplicates

You are given a string (S) consisting of lowercase alphabets. Your task is to rearrange the characters of (S) so that no two adjacent characters are identical. If such an arrangement is not possible, output (\texttt{NO}).

The common approach is to use a greedy method with a max-heap (priority queue) to always select the character with the highest remaining frequency that is not equal to the last placed character. This problem tests your knowledge in using priority queues and greedy algorithms.

inputFormat

Input is a single string (S) read from standard input. The string (S) consists of lowercase English letters and can be of length up to (10^5).

outputFormat

Output a rearranged string where no two adjacent characters are identical. If no valid rearrangement is possible, print (\texttt{NO}). The output should be written to standard output.## sample

aabb

abab