Yiit is not good with problems involved with strings and there is a problem he's having difficulties with. There is a string consisting of upper case characters \(\texttt{A}\) and \(\texttt{B}\) in the problem. In a single turn, Yiit can remove the first and the last occurrences of any character, but only if they don't coincide. Can you help Yiit and find the lexicographically smallest non-empty string that can be obtained after any number of turns?

String \(s\) is considered lexicographically smaller than \(t\) if \(s\) is a prefix of \(t\), or \(s\) has a smaller character at the first position, they differ (from left to right).

Input

The only line contains the initial string \(s\) that Yiit have.

• \(1 \le |s| \le 10^5\),
• \(s\) consists only of characters \(\texttt{A}\) and \(\texttt{B}\).

Output

Print the answer to the problem.

Example

Input:

BBABBAB

Output:

ABA

Explanation

Yiit can two times remove the first and the last occurrences of character \(\texttt{B}\) to get the string \(\texttt{ABA}\). This is the lexicographically smallest possible result they can achieve.