Attendance Record

Interview

Time limit2sMemory limit512 MB

Summary

Rearrange the letters of a record over A, B, C so the result is valid (B needs one rest day, C needs two) and lexicographically smallest.

Level: Medium6 of 10
Topics: Greedy, Brute force, Implementation, Recursion
Solved: No attempts yet

Problem

A company has three employees, named Kangho (A), Jungyu (B), and Subin (C).

Exactly one employee comes to work each day. An attendance record of "AAC" over three days means Kangho came to work on the first two days and Subin came to work on the third day.

Kangho can come to work every day. Jungyu must rest on the day after he comes to work. Subin must rest on the next two days after he comes to work. Because of these rules, some attendance records are impossible. Jungyu rests on the day after he works, so "BB" can never appear in a record.

You are given an attendance record S. Write a program that finds the lexicographically smallest valid attendance record you can build by rearranging the characters of S.

Input

The first line contains the attendance record S. S consists only of the letters A, B, and C, and its length is at most 50.

Output

Print on the first line the lexicographically smallest valid attendance record that can be built by rearranging the characters of S. The letters are ordered A < B < C. If no valid attendance record exists, print -1.

Examples4

Example 1
Input
```
CAB
```
Expected output
```
ABC
```
Example 2
Input
```
CBB
```
Expected output
```
BCB
```
Example 3
Input
```
BB
```
Expected output
```
-1
```
Example 4
Input
```
BBA
```
Expected output
```
BAB
```