14238 출근 기록

import sys
input = sys.stdin.readline
from collections import deque

record = input().rstrip()
abcCount = [0 , 0 , 0]
dpRecord = set()

def dfs(aCount , bCount , cCount , prev):

    flag = 1

    if (bCount * 2 - 1 <= sum(abcCount) and cCount * 3 - 2 <= sum(abcCount)):

        if aCount > 0 and (len(prev) <= 2 or (aCount - 1 , bCount , cCount , prev[-2] + prev[-1] + 'A') not in dpRecord):
            if len(prev + 'A') == len(record):
                print(prev + 'A')
                exit(0)
            flag = 0
            dfs(aCount - 1 , bCount , cCount , prev + 'A')
        
        if bCount > 0 and prev[-1] != 'B' and (len(prev) <= 2 or (aCount , bCount - 1, cCount , prev[-2] + prev[-1] + 'B') not in dpRecord):
            if len(prev + 'B') == len(record):
                print(prev + 'B')
                exit(0)
            flag = 0
            dfs(aCount , bCount - 1 , cCount , prev + 'B')
        
        if cCount > 0 and prev[-1] != 'C' and (len(prev) == 1 or prev[-2] != 'C') and (len(prev) <= 2 or (aCount , bCount , cCount - 1, prev[-2] + prev[-1] + 'C') not in dpRecord):
            if len(prev + 'C') == len(record):
                print(prev + 'C')
                exit(0)
            flag = 0
            dfs(aCount , bCount , cCount - 1 , prev + 'C')

    if not flag and len(prev) >= 3:
        dpRecord.add((aCount , bCount , cCount , prev[-3] + prev[-2] + prev[-1]))

for i in range(len(record)):
    if record[i] == 'A':
        abcCount[0] += 1
    elif record[i] == 'B':
        abcCount[1] += 1
    else:
        abcCount[2] += 1

if abcCount[1] * 2 - 1 > sum(abcCount):
    print(-1)
    exit(0)

if abcCount[2] * 3 - 2 > sum(abcCount):
    print(-1)
    exit(0)

if len(record) == 1:
    print(record)
    exit(0)

if abcCount[0] > 0:
    dfs(abcCount[0] - 1 , abcCount[1] , abcCount[2] , 'A')
if abcCount[1] > 0:
    dfs(abcCount[0] , abcCount[1] - 1 , abcCount[2] , 'B')
if abcCount[2] > 0:
    dfs(abcCount[0] , abcCount[1], abcCount[2] - 1 , 'C')


print(-1)