출근 기록 2

어떤 회사에 직원 세 명이 일한다. 세 사람의 이름은 강호(A), 준규(B), 수빈(C)이다.

이 회사는 하루에 한 명만 출근한다. 3일간의 출근 기록이 "AAC"라는 것은 처음 이틀은 A가 출근했고, 셋째 날은 C가 출근했다는 뜻이다.

A는 매일 출근할 수 있다. B는 출근한 다음날 반드시 쉬어야 한다. C는 출근한 다음날과 다다음날을 반드시 쉬어야 한다. 그래서 모든 출근 기록이 올바르지는 않다. 예를 들어 "BB"는 B가 이틀 연속 출근한 기록이므로 절대 나올 수 없다.

출근 기록 S가 주어진다. S의 문자를 재배열해서 만들 수 있는 올바른 출근 기록 중 사전순으로 가장 앞서는 것을 출력하는 프로그램을 작성하시오. 문자의 크기는 $A < B < C$로 비교한다.

첫째 줄에 출근 기록 S가 주어진다. S는 대문자 A, B, C로만 이루어지고, 길이는 1 이상 100,000 이하이다.

S의 문자를 그대로 재배열해서 만든 올바른 출근 기록 중 사전순으로 가장 앞서는 것을 첫째 줄에 출력한다. 올바른 출근 기록을 만들 수 없으면 -1을 출력한다.