Rearrange String

Given a string \(S\), rearrange it 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\). Note that if multiple valid answers exist, any one of them will be accepted.

For example, if \(S = aabb\) then one valid output is \(abab\), while for \(S = aaab\) the answer is \(NO\).

inputFormat

The input consists of a single line containing the string \(S\). The string \(S\) contains only lowercase English letters.

outputFormat

If a valid rearrangement exists, output one rearranged string in which no two adjacent characters are the same. Otherwise, output \(NO\).

aabb

abab