Maximize Signal Encoding

You are given a signal represented as a string. Your task is to encode this signal by rearranging its characters so that the distance between every pair of adjacent characters is maximized. In other words, after encoding, no two adjacent characters should be the same, and the reordering must be a permutation of the input characters.

The encoding strategy is as follows: first, sort the characters of the input signal in ascending order. Then, split the sorted string into two parts. The first part consists of the first \(\lceil\frac{n}{2}\rceil\) characters and the second part consists of the remaining characters. Finally, interleave these two parts by taking characters from the first part in order and characters from the second part in reverse order. The final interleaved string is the encoded signal.

For example, given the input "BRAVO", a valid encoded signal is "AVBRO".

inputFormat

The input is a single line containing the signal string \(S\) composed of uppercase English letters.

Constraints:

• 1 \(\leq |S| \leq\) 10⁵

outputFormat

Output a single line containing the encoded signal, which is a permutation of the original string \(S\) with no two adjacent characters being the same.

BRAVO

AVBRO