#include <iostream>
#include <iomanip>
#include <string.h>

using namespace std;

/* Total number of memory cells in the simulated computer */
#define NUMCELLS 8000

/* Max number of instructions to execute before simulation is declared a tie */
#define MAXINST 32000

/* Macro to calculate the number of elements in an array */
#define NUM(x) ( sizeof((x)) / sizeof(*(x)) )

/* Enumerated type for the different operand addressing modes */
typedef enum {
    M_IMM, M_DIR, M_INDIR
} admode_t;

/* Enumerated type for each possible instruction opcode */
typedef enum {
    O_DAT, O_MOV, O_ADD, O_JMP, O_JMZ, O_SLT, O_CMP
} opcode_t;

/* String mnemonics for each opcode. Must be in the same order as enum type */
char const * const mnemonics[] = {
    "DAT", "MOV", "ADD", "JMP", "JMZ", "SLT", "CMP"
};

/* String names for addressing modes; must be in the same order as enum */
char const * const modes[] = { "#" , "$", "@" };

/* Structure representing an instruction operand */
typedef struct {
    int value;       /* Numerical operand value (modulo NUMCELLS) */
    admode_t mode;   /* Addressing mode for operand (one of M_xxx enums) */
} operand_t;

/* A single memory cell which can hold one instruction */
typedef struct {
    opcode_t code;   /* Opcode; one of O_xxx enums */
    operand_t op[2]; /* The A and B operand fields */
    int modified;    /* Last warrior to modify cell; 0 if never modified */
} cell_t;

/* Handy enumerated type for accessing the cell_t's operands by name */
typedef enum { A, B } field_t;

/* This holds the contents of the simulated memory */
cell_t cell[NUMCELLS];

/*
 * Return "value" modulo NUMCELLS. The % operator is really just a division
 * remainder and not a true modulo in the mathematical sense. Therefore, this
 * function has to explicitely deal with negative values.
 */
int mod(int value)
{
    value = value % NUMCELLS;
    return (value < 0) ? value + NUMCELLS : value;
}

/* This class is an abstraction of instruction pointers */
class ip_t {
    public:
        /* Address of next instruction to be executed */ 
        int ip;      
        
        /* Get info about operands of current instruction */       
        int addr(field_t oper) const;
        int value(field_t oper, field_t field) const;
        bool imm(field_t oper) const;
        
        /* Convenient access to instruction pointer address */
        operator int() const    { return ip; }           
        void operator++(int)    { ip = mod(ip + 1); };   
        void operator=(int i)   { ip = i; };             
};

/* Each warrior needs it's own instruction pointer */
ip_t warrior[2];

/* Either 0 or 1 indicating which warrior will execute the next instruction */
int turn;

#if defined(DEBUG) || defined(STEP)
/* Print the instruction stored at location "addr" to stderr */
void print_inst(int addr)
{
    cell_t &c = cell[addr];
    
    /* Print out cell address */
    cerr << setw(4) << setfill('0') << addr << ": ";
    
    /* Print the string mnemonic */
    cerr << mnemonics[c.code];
    
    /* Print out each operand */
    for(int i = 0; i < 2; i++) {
        cerr << "  " << modes[ c.op[i].mode ] << setw(4) << c.op[i].value;
    }
    
    /* Print the warrior number that modified this cell last */
    if(c.modified) {
        cerr << "  (" << c.modified << ")";
    } else {
        cerr << "     ";
    }

    /* Show instruction pointers if they are at this location */
    for(int i = 0; i < 2; i++) {
        if(warrior[i] == addr) {
            cerr << "  <==" << i + 1 << "==";
        }
    }

    cerr << endl;
}

/* Dump the contents of all simulated memory. Used for DEBUG only */
void dump()
{
    /* Print cells only if modified or pointed to by instruction pointers */
    for(int addr = 0; addr < NUMCELLS; addr++) {
        if(cell[addr].modified || warrior[0] == addr || warrior[1] == addr) {
            print_inst(addr);
        }
    }
}
#endif

/*
 * Update the "field" field of an instruction at address "addr" with "value"
 * modulo NUMCELLS. We keep track of which warrior modified the cell (for
 * DEBUG purposes).
 */
void op_write(int addr, int field, int value)
{
    cell_t &c = cell[addr];

    c.op[field].value = mod(value);
    c.modified = turn + 1;
}

/*
 * Copy the entire instruction at absolute address "src" to absolute address
 * "dst". We keep track of which warrior modified the destination cell (for
 * DEBUG purposes).
 */
void op_copy(int dst, int src)
{
    cell_t &c = cell[dst];
 
    c.code = cell[src].code;
    c.op[A] = cell[src].op[A];
    c.op[B] = cell[src].op[B];
    c.modified = turn + 1;
}

/*
 * Return true if the instructions at locations "addr1" and "addr2" are
 * identical. One instruction is considered equal to another if they have the
 * same opcode, same field values, and same operand addressing modes.
 */
bool op_equal(int addr1, int addr2)
{
    cell_t &c1 = cell[addr1];
    cell_t &c2 = cell[addr2];

    /* Check if opcodes match */
    if(c1.code != c2.code) {
        return false;
    }
    
    /* Check if operands match in value and addressing modes */
    for(int i = 0; i < 2; i++) {
        if(c1.op[i].value != c2.op[i].value || c1.op[i].mode != c2.op[i].mode) {
            return false;
        }            
    }

    return true;
}

/*
 * For the currently executing instruction, return the absolute address that
 * it's operand "oper" is pointing to. This is only valid for direct or
 * indirect operands; immediate operands contain a literal value and not an
 * address. Address calculations involving direct addressing mode are done
 * relative to the current instruction pointer. For indirect addressing,
 * the calculations are done relative to the instruction address who's B
 * field stores the indirect address.
 */
int ip_t::addr(field_t oper) const
{
    int value;
    
    /* Operand selected by "oper" argument */
    operand_t &o = cell[ip].op[oper];
    
    /* Check the operand's addressing mode */
    switch(o.mode) {

        /* Cannot return address for an immediate operand */
        case M_IMM:
            throw "Illegal addressing mode";
            break;
            
        /* Direct addressing simply performs the address arithmetic */
        case M_DIR:
            value = mod(ip + o.value);
            break;
            
        /* Indirect requires a dereference to get the address */
        case M_INDIR:
            int indir = mod(ip + o.value);
            value = cell[indir].op[B].value;
            value = mod(indir + value);
            break;
    }
    
    return value;
}

/*
 * For the currently executing instruction, return the value that it's operand
 * "oper" is accessing. This function takes care of dereferencing the
 * different addressing modes. If the operand uses direct/indirect addressing,
 * then this returns the requested "field" value of the instruction pointed to
 * by the operand.
 */
int ip_t::value(field_t oper, field_t field) const
{
    int value;

    /* Operand selected by "oper" argument */
    operand_t &o = cell[ip].op[oper];
    
    /* For immediate addressing, simply return the literal value */
    if(o.mode == M_IMM) {
        value = o.value;
    }
    
    /* For other modes, return requested "field" that's pointed to by "oper" */
    else {
        value = cell[ addr(oper) ].op[field].value;
    }

    return value;
}

/* Return true if current instruction's "oper" operand is immediate */
bool ip_t::imm(field_t oper) const
{
    return (cell[ip].op[oper].mode == M_IMM) ? true : false;
}

/*
 * Execute a single instruction at given instruction pointer. This function
 * actually decodes each opcode and carries out all its side effects. Returns
 * true if a DAT instruction was executed; returns false otherwise. This
 * function also updates the IP as needed.
 */
bool execute(ip_t &ip)
{
    /* Check the opcode of the currently executing instruction */
    switch(cell[ip].code) {

        /* Executing DAT will immediately halt the simulation */
        case O_DAT:
            return true;

        /* Copy value/instruction at A to location B */
        case O_MOV:
        
            /* If A is immediate, copy the value to B field of location B */
            if( ip.imm(A) ) {
                op_write( ip.addr(B), B, ip.value(A, A) );
            }
            
            /* Otherwise copy entire instruction at location A to location B */
            else {
                op_copy( ip.addr(B), ip.addr(A) );
            }
            
            ip++;
            break;

        /* Add A and/or B fields and store results in location B */
        case O_ADD:
        
            /* If A is immediate, add and store to B field of location B */
            if( ip.imm(A) ) {
                op_write( ip.addr(B), B, ip.value(A, A) + ip.value(B, B) );
            }
            
            /* Otherwise add both fields of both locations and store in B */
            else {
                op_write( ip.addr(B), A, ip.value(A, A) + ip.value(B, A) );
                op_write( ip.addr(B), B, ip.value(A, B) + ip.value(B, B) );
            }
            
            ip++;
            break;

        /* Jump to address at A */
        case O_JMP:
            ip = ip.addr(A);
            break;

        /* Jump to address at A if B field of location B is zero */
        case O_JMZ:
        
            /* If B field of location B is zero then jump */
            if( ip.value(B, B) == 0 ) {                
                ip = ip.addr(A);
            }
            
            /* Otherwise, continue execution with the next instruction */
            else {
                ip++;
            }
            
            break;

        /* Skip if value specified by A is less than B field of location B */
        case O_SLT:
            if( ip.value(A, B) < ip.value(B, B) ) {
                ip++;
            }
            
            ip++;
            break;

        /* Skip if instructions at location A and B are identical */
        case O_CMP:
            if(op_equal( ip.addr(A), ip.addr(B) )) {
                ip++;
            }
            
            ip++;
            break;

    }
    
    /* Return false if no DAT was executed */
    return false;
}

/*
 * Run core wars simulation by alternatively executing program instructions.
 * Returns 1 or 2 depending on which warrior program is the winner (i.e
 * the other program executed a DAT). Returns 0 in case of a tie (i.e. 
 * maximum number of instruction reached without executing any DAT).
 */
int simulate(void)
{
    int inst_count;

    /* Execution always starts with warrior number one */
    turn = 0;

    /* Keep running until max instruction count is reached or a DAT executes */
    for(inst_count = 0; inst_count < MAXINST; inst_count++) {

#ifdef STEP
        cerr << "Cycle #" << inst_count;
        cerr << " Program #" << turn + 1 << " about to execute" << endl;
        dump();
#endif

        /* Execute one instruction; if DAT is executed, other program wins */
        if( execute(warrior[turn]) ) {
            return (turn ? 0 : 1) + 1;
        }
    
        /* Alternate between warrior programs */
        turn = (turn ? 0 : 1);
    }
    
    /* If max instruction count reached, then this match is a tie */
    return 0;
    
}

/*
 * Search the given string "array" with "count" elements for matching "str".
 * Returns the index into "array" which matches "str". Used to parse opcode
 * mnemonics and operand addressing modes. Since string arrays passed contain
 * strings in the same order as the corresponding enums, the return value of
 * this function can be directly type cast to the appropriate enum value.
 */
int parse_str(string const &str, char const * const array[], int count)
{
    /* Search the array for "str" and return matching index */
    for(int i = 0; i < count; i++) {
        if(str == array[i]) {
            return i;
        }
    }
    
    /* If we reached here, the the string wasn't found */
    throw "Unknown string on input";
}

/* Read in a single operand and assign to "op" operand field */
void parse_operand(operand_t &op)
{
    string str;

    /* Read in and parse addressing mode character */
    cin >> setw(1) >> str;
    op.mode = (admode_t) parse_str(str, modes, NUM(modes));

    /* Parse operand value and normalize since it could have been negative */
    cin >> op.value;
    op.value = mod(op.value);
}

/*
 * Read in the starting address and instruction stream for a warrior, and load
 * the instructions into the "cell" array. The "program" parameter is either
 * 0 or 1 depending on which warrior program is being loaded. This number is
 * used to keep track of which instructions belong to each warrior and to
 * update the correct instruction pointer to the start of the loaded program.
 */
void parse_code(int program)
{
    int start, addr, inst_idx, inst_count;
    
    /* Read the instruction count for the warrior program */
    cin >> inst_count;

    /* Read in the address at which to start loading warrior program */
    cin >> addr;
    warrior[program] = addr;
    
    /* Parse one instruction at a time, loading it into memory */
    for(inst_idx = 0; inst_idx < inst_count; inst_idx++) {
        string str;

        /* Read and parse opcode mnemonic from input */
        cin >> str;        
        cell[addr].code = (opcode_t) parse_str(str, mnemonics, NUM(mnemonics));
        
        /* Mark instructions as belonging to warrior (for DEBUG only) */
        cell[addr].modified = program + 1;

        /* Parse both operands */
        parse_operand( cell[addr].op[A] );
        parse_operand( cell[addr].op[B] );
        
        /*
         * Increment instruction address modulo NUMCELLS. If the warrior is
         * loaded at the end of simulated memory, the instructions continue
         * loading back at the beginning of memory.
         */
        addr = mod(addr + 1);
    }
}

/* Main body of program */
void process(void)
{
    int game_num, game_idx;

    /* Read how many games are to be simulated */
    cin >> game_num;
    
    /* Process each game separately */
    for(game_idx = 0; game_idx < game_num; game_idx++) {
    
        /*
         * Clear all simulated memory. Filling the cell array with zeroes is
         * equivalent to filling all cells with "DAT #0 #0" instructions
         */
        memset(cell, 0, sizeof(cell));
        
        /* Parse both warrior programs */
        parse_code(0);
        parse_code(1);
        
        /* Run core wards simulation to completion */
        int status = simulate();

        /* Print the results */
        if(status == 0) {
            cout << "Programs are tied." << endl;
        } else {
            cout << "Program #" << status << " is the winner." << endl;
        }

#if defined(DEBUG) || defined(STEP)
        dump();
#endif
    }
}

/* Run program and print out any exceptions that occur */
int main(void)
{
    /* Throw exceptions on EOF or failed data extraction in >> operator */
    cin.exceptions(ios::eofbit | ios::failbit);

    /* Run main body of code */
    try {
        process();
    }
    
    /* Catch any internally generated exceptions */
    catch(char const *e) {
        cerr << "Exception: " << e << endl;
    }
    
    /* Catch unexpected EOF or bad input data */
    catch(ios::failure const &e) {
        cerr << "Unexpected EOF or data type mismatch on input" << endl;
    }

    return 0;
}