def add(m, state, md, x, y, o):
    m = store(m, state, md[2], o, load(m, state, md[0], x) + load(m, state, md[1], y))
    return (state[0] + 4, state[1])

def mult(m, state, md, x, y, o):
    m = store(m, state, md[2], o, load(m, state, md[0], x) * load(m, state, md[1], y))
    return (state[0] + 4, state[1])

def halt(m, state, md):
    return (-1, state[1])

def readint(m, state, md, x, external_input):
    m = store(m, state, md[0], x, external_input)
    return (state[0] + 2, state[1])

def output(m, state, md, x):
    #print("out: ", load(m, md[0], x))
    return ((state[0] + 2, state[1]), load(m, state, md[0], x))

def jmpt(m, state, md, a, jpa):
    addr = load(m, state, md[1], jpa) if load(m, state, md[0], a) != 0 else state[0] + 3
    return (addr, state[1])

def jmpf(m, state, md, a, jpa):
    addr = load(m, state, md[1], jpa) if load(m, state, md[0], a) == 0 else state[0] + 3
    return (addr, state[1])

def lt(m, state, md, a, b, o):
    store(m, state, md[2], o, 1 if load(m, state, md[0], a) < load(m, state, md[1], b) else 0)
    return (state[0] + 4, state[1])

def eq(m, state, md, a, b, o):
    store(m, state, md[2], o, 1 if load(m, state, md[0], a) == load(m, state, md[1], b) else 0)
    return (state[0] + 4, state[1])

def chrb(m, state, md, x):
    return (state[0] + 2, state[1] + load(m, state, md[0], x))

def digits(num, length):
    return list(map(lambda x: int(x), list(str(num).zfill(length))))

def load(m, state, mode, val):
    if mode == 0:
        # print(val in m, m)
        if val in m:
            # print(val)
            return m[val]
        else:
            return 0
    elif mode == 1:
        return val
    elif mode == 2:
        if (state[1] + val) in m:
            return m[state[1] + val]
        else:
            return 0


def store(m, state, mode, addr, val):
    if mode == 0:
        m[addr] = val
    elif mode == 1:
        raise Exception("invalid mode")
    elif mode == 2:
        m[state[1] + addr] = val

    return m

def memslice(mem, fr, to):
    return [ mem[i] for i in range(fr, to) ]

OPCODES = {
    1: (3, add),
    2: (3, mult),
    3: (1, readint),
    4: (1, output),
    5: (2, jmpt),
    6: (2, jmpf),
    7: (3, lt),
    8: (3, eq),
    9: (1, chrb), # change relative base
    99: (0, halt)
}

def printOp(op, mem, state, modes, params):
    paramStr = []

    for i in range(len(params)):
        if modes[i] == 0:
            md = "i"
        elif modes[i] == 1:
            md = ""
        elif modes[i] == 2:
            md = "r"

        dbgVal = ""

        if modes[i] == 0 or modes[i] == 2:
            try:
                val = load(mem, state, modes[i], params[i])
            except:
                val = "<none>"
            dbgVal = "~({})".format(val)

        paramStr.append("{}:{}{}".format(md, params[i], dbgVal))

    if op == 1:
        opStr = "add"
    elif op == 2:
        opStr = "mult"
    elif op == 3:
        opStr = "read"
    elif op == 4:
        opStr = "outp"
    elif op == 5:
        opStr = "jmpt"
    elif op == 6:
        opStr = "jmpf"
    elif op == 7:
        opStr = "lt"
    elif op == 8:
        opStr = "eq"
    elif op == 9:
        opStr = "chrb"
    elif op == 99:
        opStr = "halt"

    print("{} ({})".format(opStr, ", ".join(paramStr)))

def defaultInputFn():
    return int(input("Enter integer: "))

def runIntcode(initial_memory, mem_parameters=[], input_parameters=[], ret="output"):
    mem = { i: val for i, val in enumerate(initial_memory) }
    output_values = []

    # for i,v in enumerate(initial_memory):
    #     print("{:3d}: {}".format(i, v))

    ip = 0
    rb = 0 # relative base

    state = (ip, rb)

    for (addr, val) in mem_parameters:
        mem[addr] = val

    while True:
        ip, rb = state

        op_full = mem[ip]

        op = op_full % 100

        length, fn = OPCODES[op]
        modes = list(reversed(digits(op_full, length+2)[:-2]))

        # print(op, modes, mem[ip+1:ip+1+length])
        # printOp(op, modes, memslice(mem, ip+1, ip+1+length))

        if op == 3:
            if len(input_parameters) > 0:
                state = fn(mem, state, modes, *memslice(mem, ip+1, ip+1+length), input_parameters.pop(0))
            else:
                state = fn(mem, state, modes, *memslice(mem, ip+1, ip+1+length), int(input("Enter integer: ")))
        elif op == 4:
            state, output = fn(mem, state, modes, *memslice(mem, ip+1, ip+1+length))
            output_values.append(output)
        else:
            state = fn(mem, state, modes, *memslice(mem, ip+1, ip+1+length))

        if state[0] == -1:
            break

    if ret == "output":
        return output_values
    elif ret == "mem0":
        return mem[0]

def runIntcodeGen(initial_memory, input_queue=list(), mem_parameters=[], input_generator=None, input_fn=defaultInputFn, print_inputs=False, print_input_ascii=False, always_yield=False ):
    mem = { i: val for i, val in enumerate(initial_memory) }

    ip = 0
    rb = 0 # relative base

    state = (ip, rb)

    for (addr, val) in mem_parameters:
        mem[addr] = val

    while True:
        ip, rb = state

        op_full = mem[ip]

        op = op_full % 100

        length, fn = OPCODES[op]
        modes = list(reversed(digits(op_full, length+2)[:-2]))

        # print(op, modes, memslice(mem, ip+1, ip+1+length))
        # printOp(op, mem, state, modes, memslice(mem, ip+1, ip+1+length))

        if op == 99:
            print("HALT CALLED")

        if op == 3:
            if input_generator is not None:
                in_val = next(input_generator)
            elif len(input_queue) > 0:
                in_val = input_queue.pop(0)
            else:
                in_val = input_fn()

            if print_inputs:
                print(chr(in_val) if print_input_ascii else in_val, end="")

            state = fn(mem, state, modes, *memslice(mem, ip+1, ip+1+length), in_val)

            if always_yield:
                yield None
        elif op == 4:
            state, output = fn(mem, state, modes, *memslice(mem, ip+1, ip+1+length))
            yield output
        else:
            state = fn(mem, state, modes, *memslice(mem, ip+1, ip+1+length))
            if always_yield:
                yield None

        if state[0] == -1:
            break