cho.sh

Attendance Record 2

Given a string of A, B, C, rearrange its letters into the lexicographically smallest valid schedule where B needs a rest day after working and C needs two.

Medium6GreedyStringImplementationSortingInterviewNo attempts yetTime limit2sMemory limit512 MB

Problem

Three employees work at a company. Their names are Kangho (A), Jungyu (B), and Subin (C).

Exactly one employee comes to work each day. A three day record of "AAC" means A worked on the first two days and C worked on the third day.

A can work every day. B must rest on the day after working. C must rest on the next two days after working. So not every record is valid. For example, "BB" never appears, because it puts B at work on two days in a row.

You are given an attendance record S. Rearrange the letters of S and print the valid record that comes first in lexicographic order, comparing letters as A<B<CA < B < C.

Input

The first line contains the attendance record S. S consists only of the uppercase letters A, B, and C, and its length is at least 1 and at most 100,000.

Output

Print the lexicographically smallest valid attendance record that uses exactly the letters of S. If no rearrangement of S is a valid record, print -1.