def extract_pairs(line):
    original, encoded = line.split(" -> ")
    return original, encoded

def find_possible_positions(original, encoded):
    positions = {}
    for i in range(len(original)):
        for j in range(len(encoded)):
            if original[i] == encoded[j]:
                if i not in positions:
                    positions[i] = []
                positions[i].append(j)
    return positions

def find_common_positions(positions_1, positions_2):
    common_positions = {}
    for idx in positions_1:
        if idx in positions_2:
            common_positions[idx] = list(set(positions_1[idx]) & set(positions_2[idx]))
    return common_positions

def decode(encoded, common_positions):
    original = ['?'] * len(encoded)
    for i in range(len(encoded)):
        if i in common_positions and common_positions[i]:
            original[i] = encoded[common_positions[i][0]]
    return ''.join(original)

def format_table(data, headers):
    col_widths = [max(len(str(item)) for item in col) for col in zip(headers, *data)]
    header_line = " | ".join(f"{header:<{col_widths[i]}}" for i, header in enumerate(headers))
    separator_line = "-+-".join('-' * col_widths[i] for i in range(len(headers)))
    data_lines = [" | ".join(f"{str(item):<{col_widths[i]}}" for i, item in enumerate(row)) for row in data]
    return "\n".join([header_line, separator_line] + data_lines)

if __name__ == "__main__":
    # Read input from file and process
    with open('input.txt', 'r') as file:
        lines = [line.strip() for line in file]

    if len(lines) < 3:
        print("File does not contain enough data.")
    else:
        # Extract original and encoded pairs from the first two examples
        original_1, encoded_1 = extract_pairs(lines[0])
        original_2, encoded_2 = extract_pairs(lines[1])

        # Find possible positions for permutation
        positions_1 = find_possible_positions(original_1, encoded_1)
        positions_2 = find_possible_positions(original_2, encoded_2)

        # Find common positions for permutation
        common_positions = find_common_positions(positions_1, positions_2)

        # Prepare data for the table
        table = []
        for idx in range(len(original_1)):
            pos_1 = [f"{p:02}" for p in positions_1.get(idx, [])]
            pos_2 = [f"{p:02}" for p in positions_2.get(idx, [])]
            common_pos = [f"{p:02}" for p in common_positions.get(idx, [])]
            table.append([f"{idx:02}", pos_1, pos_2, common_pos])

        # Define headers
        headers = ["Index", "String 1", "String 2", "Possible Perm"]

        # Print the table
        print("Possible positions and possible perm:")
        print(format_table(table, headers))

        # Extract the encoded string from the third example
        encoded_3 = extract_pairs(lines[2])[1]

        # Decode the third encoded string
        original_3 = decode(encoded_3, common_positions)

        print(f"\nEncoded string: {encoded_3}")
        print(f"Decoded string: {original_3}")



## ---

# Output:

#   Possible positions and possible perm:
# Index | String 1                 | String 2                 | Possible Perm
# ------+--------------------------+--------------------------+--------------
# 00    | ['02', '06', '13', '15'] | ['02', '03', '12', '14'] | ['02']       
# 01    | ['02', '06', '13', '15'] | ['00', '05', '09', '15'] | ['15']       
# 02    | ['02', '06', '13', '15'] | ['01', '07', '10', '13'] | ['13']       
# 03    | ['02', '06', '13', '15'] | ['04', '06', '08', '11'] | ['06']       
# 04    | ['07', '09', '11', '12'] | ['02', '03', '12', '14'] | ['12']       
# 05    | ['07', '09', '11', '12'] | ['00', '05', '09', '15'] | ['09']       
# 06    | ['07', '09', '11', '12'] | ['01', '07', '10', '13'] | ['07']       
# 07    | ['07', '09', '11', '12'] | ['04', '06', '08', '11'] | ['11']       
# 08    | ['00', '01', '03', '04'] | ['02', '03', '12', '14'] | ['03']       
# 09    | ['00', '01', '03', '04'] | ['00', '05', '09', '15'] | ['00']       
# 10    | ['00', '01', '03', '04'] | ['01', '07', '10', '13'] | ['01']       
# 11    | ['00', '01', '03', '04'] | ['04', '06', '08', '11'] | ['04']       
# 12    | ['05', '08', '10', '14'] | ['02', '03', '12', '14'] | ['14']       
# 13    | ['05', '08', '10', '14'] | ['00', '05', '09', '15'] | ['05']       
# 14    | ['05', '08', '10', '14'] | ['01', '07', '10', '13'] | ['10']       
# 15    | ['05', '08', '10', '14'] | ['04', '06', '08', '11'] | ['08']       

# Encoded string: owuwspdgrtejiiud
# Decoded string: udiditgjwowsuper