#!/usr/bin/env python3
import sys
from collections import defaultdict
from typing import Tuple, Dict, Any

def parse_line(line: str) -> Tuple[str, Dict[str, Any]]:
    """
    Parse a line of output from the pintool, returning the name of the
    executed action along with its parameters.
    """
    # Example line: strcmp; n=0 taint=34 cmp_val=65
    action, rest = line.split('; ')
    parameters = {}
    for kvpair in rest.split():
        key, val = kvpair.split('=')

        try:
            val = int(val)
        except ValueError:
            pass

        parameters[key] = val
    return (action, parameters)


def main():
    UNKNOWN_VAL = -42

    # The deduced contents of id_mars1
    deduced_input = [UNKNOWN_VAL] * 1601

    # List of operations to undo for a given comparison value.
    backtracks = defaultdict(list)

    # Handle the operations that are logged by the pintool.
    for line in sys.stdin.readlines():
        line = line.strip()

        if not ';' in line:
            continue

        action, parameters = parse_line(line)

        if action == 'cmp reg to reg':
            deduced_input[parameters['taint_1']] = parameters['cmp_val_2']
        elif action == 'strcmp' or action.startswith('cmp'):
            taint = parameters['taint']
            val = parameters['cmp_val']
            deduced_input[taint] = val
        elif action.startswith('arith') and parameters['op'] == 'XOR':
            taint, xor_val = parameters['taint_dst'], parameters['val_src']
            backtracks[taint].insert(0, ('xor', xor_val))
        elif action == 'arith (reg to reg)':
            op = parameters['op']
            if op == 'ADD':
                if not parameters['taint_dst'] == 0: continue
                backtracks[parameters['taint_src']].insert(0, ('add', parameters['val_dst']))
            elif op == 'SUB':
                if not parameters['taint_src'] == 0: continue
                backtracks[parameters['taint_dst']].insert(0, ('sub', parameters['val_src']))
            elif op == 'SHL':
                assert parameters['taint_src'] == 0
                backtracks[parameters['taint_dst']].insert(0, ('shl', parameters['val_src']))
            elif op == 'SHR':
                assert parameters['taint_src'] == 0
                backtracks[parameters['taint_dst']].insert(0, ('shr', parameters['val_src']))

    # Backtrack, reversing operations done to tainted values.
    for k, v in backtracks.items():
        for (op, arg) in v:
            if op == 'xor':
                deduced_input[k] ^= arg
            if op == 'add':
                deduced_input[k] -= arg
            if op == 'sub':
                deduced_input[k] += arg
            if op == 'shl':
                deduced_input[k] >>= arg
            if op == 'shr':
                deduced_input[k] <<= arg

    # Generate the deduced input, replacing unknown bytes with asterisks
    generated_input = ''.join(chr(c) if c != UNKNOWN_VAL else '*' for c in deduced_input[1:])
    print(generated_input, end='')

main()
