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


import ovcc_grader

original_equation = ""
output_equation = ""
element1 = ['A', 'A', '~A', '~A']
element2 = ['B', '~B']
element3 = ['~C', 'C', 'C', '~C']

def pretty_print_2D(T):
  cols =len(T[0])
  lens = [cols for i in range(0,cols)]
  fmt = ' '.join('{{:{}}}'.format(x) for x in lens)
  table = [fmt.format(*row) for row in T]
  print('\n'.join(table))

def hexToBinary(N):
   # Code to convert hex to binary
   res = "{0:08b}".format(int(N, 16))
   return res

def listToMatrix(N):
    li = list(out)
    T = []
    while li != []:
        T.append(li[:4])
        li = li[4:]
    return T


def find_groups_of_4(T, output_equation):
    rows = len(T)
    cols = len(T[0])
    M = [[0 for j in range(cols)] for i in range(rows)]
    M = T

    # find group of 4 top row and bottom row
    for r in range(0, rows):
        count = 0

        for c in range(0, cols):

            if int(M[r][c]) == 1:
                count = count + 1
            else:
                count = 0

            if count == 4:
                for i in range(0, cols):
                    M[r][i] = '0'

                if output_equation == "":
                    output_equation += element2[r]

                elif output_equation == element2[0]:
                        # complement law if we find group of 4 in both rows
                        output_equation = '1'
                else:
                        output_equation += '+'
                        output_equation += element2[r]

     # find group of 4 in columns
    for c in range(0, cols):

        if int(M[0][c]) == 1 and c < cols - 1 :
            if int(M[0][c+1]) == 1 :
                if int(M[1][c]) == 1 and int(M[1][c+1]) == 1 :
                    count = 4
                    M[0][c] = '0'
                    M[0][c+1] = '0'
                    M[1][c] = '0'
                    M[1][c+1] = '0'

                    if output_equation != "":
                        output_equation += '+'
                    if c == 0:
                        output_equation += element1[c]
                    elif c == 1:
                        output_equation += element3[c]
                    elif c == 2:
                        output_equation += element1[c]

    return M, output_equation

def find_groups_of_4_withwrap(T, output_equation):
    rows = len(T)
    cols = len(T[0])
    M = [[0 for j in range(cols)] for i in range(rows)]
    M = T

     # find group of 4 in columns
    for c in range(0, cols):
        if c == 0 and int(M[0][c]) == 1 and int(M[0][cols - 1]) == 1 :
            if int(M[1][c]) == 1 and int(M[1][cols - 1]) == 1 :
                M[0][c] = '0'
                M[0][cols - 1] = '0'
                M[1][c] = '0'
                M[1][cols - 1] = '0'
                if output_equation != "":
                    output_equation += '+'
                if c == 0:
                    output_equation += element3[c]

    return M, output_equation

def find_groups_of_2(T, output_equation):
    rows = len(T)
    cols = len(T[0])
    M = [[0 for j in range(cols)] for i in range(rows)]
    M = T
    for r in range(0, rows):
        count = 0

        #check for group 2: top row left to right, bottom row left to right
        for c in range(0, cols):
            if int(M[r][c]) == 1:
                count = count + 1
            else:
                count = 0

            if count == 2:
                M[r][c-1] = '0'
                M[r][c] = '0'

                if output_equation != "":
                    output_equation += '+'
                if c == 1 or c == 3:
                    output_equation += element1[c]
                if r == 0 or r == 1:
                    output_equation += element2[r]
                if c == 2 :
                    output_equation += element3[c]

    #check for group 2: columns from left to right
    for c in range(0, cols):
        count = 0

        if int(M[0][c]) == 1 and int(M[1][c]) == 1:
            count = 2
        else:
            count = 0

        if count == 2:
            M[0][c] = '0'
            M[1][c] = '0'
            if output_equation != "":
                output_equation += '+'

            output_equation += element1[c]
            output_equation += element3[c]


    return M, output_equation

def find_groups_of_2_withwrap(T, output_equation):

        rows = len(T)
        cols = len(T[0])
        M = [[0 for j in range(cols)] for i in range(rows)]
        M = T
        # check for group 2 end column adjacent X's
        for r in range(0, rows):
            count = 0

            if int(M[r][0]) == 1 and int(M[r][cols - 1]) == 1:
                    count = 2
            else:
                count = 0

            if count == 2:
                M[r][0] = '0'
                M[r][cols - 1] = '0'

                if output_equation != "":
                    output_equation += '+'

                output_equation += element2[r]
                output_equation += element3[0]


        return M, output_equation

def find_single_terms(T, output_equation):

        rows = len(T)
        cols = len(T[0])
        M = [[0 for j in range(cols)] for i in range(rows)]
        M = T
        for r in range(0, rows):

            # check for group 2: top row left to right, bottom row left to right
            for c in range(0, cols):

                if int(M[r][c]) == 1:
                    M[r][c] = '0'

                    if output_equation != "":
                        output_equation += '+'

                    output_equation += element1[c]
                    output_equation += element2[r]
                    output_equation += element3[c]


        return M, output_equation

def printEquation(T, original_equation):
  rows = len(T)
  cols = len(T[0])
  M = [[0 for j in range(cols)] for i in range(rows)]
  M = T
  for r in range(0,rows):
      for c in range(0, cols):
          if (int(M[r][c]) == 1):
              if original_equation != "":
                 original_equation += '+'
              original_equation += element1[c]
              original_equation += element2[r]
              original_equation += element3[c]
  return original_equation


################################################
# main program
################################################

input = ovcc_grader.readinput()
ovcc_grader.clearoutput()
for line in input:
    N = str(line[0])
    out = hexToBinary(N)
    T = listToMatrix(out)

    #pretty_print_2D(T)
    #original_equation = printEquation(T, original_equation )
    #print (original_equation)
    #original_equation = ""

    M, output_equation = find_groups_of_4(T, output_equation)
    M, output_equation = find_groups_of_4_withwrap(M, output_equation)
    M, output_equation = find_groups_of_2(M, output_equation)
    M, output_equation = find_groups_of_2_withwrap(M, output_equation)
    M, output_equation = find_single_terms(M, output_equation)

    #corner case if input has no 1's in input number
    if output_equation == "": output_equation = '0'

    ovcc_grader.writeoutput(output_equation)
    output_equation = ""