# -----------------------------------------------------------------------------------------
# Oak Valley Coding Club 2019-2020
# Solution for 2020 ACSL Programming Problem #3 – Junior Division
# Author :  Mihir Sood
# Language: Python 3.x
# -----------------------------------------------------------------------------------------


import ovcc_grader_strings

#---------------------------------------------------------------------------------------------------
def toBin4(ini_string):
    return bin(int(ini_string, 16)).zfill(4)[-4:].replace('b','0')

def squareScan(T):
    whichrow = 0
    whichcolumn = 0
    output = []
    outty = True
    while outty:
        if whichcolumn == 3:
            outty = False
            if T[whichrow][whichcolumn] == '1' and T[whichrow+1][whichcolumn] == '1' and T[whichrow][-4] == '1' and T[whichrow+1][-4] == '1':
                T[whichrow][whichcolumn] = 'd'
                T[whichrow+1][whichcolumn] = 'd'
                T[whichrow][-4] = 'd'
                T[whichrow+1][-4] = 'd'
                output.append('~C')
        else:
            if T[whichrow][whichcolumn] == '1' and T[whichrow+1][whichcolumn] == '1' and T[whichrow][whichcolumn+1] == '1' and T[whichrow+1][whichcolumn+1] == '1':
                T[whichrow][whichcolumn] = 'd'
                T[whichrow+1][whichcolumn] = 'd'
                T[whichrow][whichcolumn+1] = 'd'
                T[whichrow+1][whichcolumn+1] = 'd' 
                if whichcolumn == 0:
                    output.append('A')
                elif whichcolumn == 1:
                    output.append('C')
                else:
                    output.append('~A')
                
        whichcolumn = whichcolumn + 1
    return output

def lineScan(T):
    whichrow = 0
    output = []
    outty = True
    while outty:
        if whichrow == 1:
            outty = False
        if T[whichrow] == ['1','1','1','1']:
            T[whichrow] = ['d','d','d','d']
            if whichrow == 0:
                output.append('B')
            else:
                output.append("~B")
        whichrow = whichrow + 1
    return output


def twoScan(T):
    outty = True
    whichrow = 0
    whichcolumn = 0
    Onecheck = 0
    output = []
    while outty:
        if whichcolumn == 3 and whichrow == 1:
            outty = False
        if T[whichrow][whichcolumn] == '1':
            if Onecheck == 1:
                T[whichrow][whichcolumn-1] = 'd'
                T[whichrow][whichcolumn] = 'd'
                parts = []
                if whichrow == 0:
                    parts.append('B')
                else:
                    parts.append('~B')
                if whichcolumn == 1:
                    parts.insert(0,'A')
                elif whichcolumn == 2:
                    parts.append('C')
                elif whichcolumn == 3:
                    parts.insert(0,'~A')
                output.append(''.join(parts))
                Onecheck = 0
            else:
                Onecheck = 1
        else:
            Onecheck = 0
            
        if whichcolumn == 3:
            whichcolumn = 0
            whichrow = whichrow + 1
            Onecheck = 0
        else:
            whichcolumn = whichcolumn + 1
    whichrow = 0
    whichcolumn = 0
    Onecheck = 0
    outty = True
    while outty:
        if whichrow + whichcolumn == 4:
            outty = False
        if T[whichrow][whichcolumn] == '1':
            if Onecheck == 1:
                T[0][whichcolumn] = 'd'
                T[1][whichcolumn] = 'd'
                if whichcolumn == 0:
                    output.append("A~C")
                elif whichcolumn == 1:
                    output.append("AC")
                elif whichcolumn == 2:
                    output.append("~AC")
                else:
                    output.append("~A~C")
            Onecheck = 1
        else:
            Onecheck = 0
            
        if whichrow == 1:
            whichrow = 0
            whichcolumn = whichcolumn + 1
            Onecheck = 0      
        else:
            whichrow = whichrow + 1

    if T[0][3] == '1' and T[0][0] == '1':
        output.append("B~C")
        T[0][3] = 'd'
        T[0][0] = 'd'
    if T[1][3] == '1' and T[1][0] == '1':
        output.append("~B~C")
    return output

def oneScan(T):
    whichrow = 0
    whichcolumn = 0
    output = []
    outty = True
    while outty:
        if whichcolumn == 3 and whichrow == 1:
            outty = False
        if T[whichrow][whichcolumn] == '1':
            parts = []
            if whichcolumn == 0:
                parts.append('A')
                parts.append("~C")
            elif whichcolumn == 1:
                parts.append("A")
                parts.append("C")
            elif whichcolumn == 2:
                parts.append("~A")
                parts.append("C")
            else:
                parts.append("~A")
                parts.append("~C")
            if whichrow == 0:
                parts.insert(1,"B")
            else:
                parts.insert(1,"~B")
            output.append("".join(parts))
            parts = []
            T[whichrow][whichcolumn] = 'd'
        if whichcolumn == 3:
                whichcolumn = 0
                whichrow = whichrow + 1
                Onecheck = 0
        else:
            whichcolumn = whichcolumn + 1
    return output

def main(ini_string):
    output = None
    if ini_string != '00' and ini_string.lower() != 'ff':
        T = [list(toBin4(ini_string[0])),list(toBin4(ini_string[1]))]
        output = ' + '.join(lineScan(T) + squareScan(T) + twoScan(T) + oneScan(T))
    elif ini_string.lower() == 'ff':
        output = 1
    else:
        output = 0
    
    return output

#--------------------------------------------------------------------------------------------------------
input = ovcc_grader_strings.readinput()

ovcc_grader_strings.clearoutput()
for line in input:
    ini_string = line[0]
    ovcc_grader_strings.writeoutput(main(ini_string))
    print(main(ini_string))