Reorganize String

Given a string s consisting of lowercase English letters, your task is to reorder the characters of s so that no two adjacent characters are the same. If such a reordering is possible, print any valid rearrangement; otherwise, print an empty string.

Formally, let s be a string of length n. You need to produce a permutation s‑' of the characters of s such that for all indices \(1 \le i < n\), the condition \(s'_{i} \neq s'_{i+1}\) holds. If there is no solution, output an empty string.

Note: If multiple reordering exist, any valid answer will be accepted.

inputFormat

The input consists of a single line read from standard input containing the string s.

Constraints: s contains only lowercase English letters.

outputFormat

Output a valid reordering of the string such that no two adjacent characters are the same. If no such reordering exists, output an empty string.

aaabbc

ababac