from typing import List
from typing import Tuple


def run(code: List[Tuple[str, int]]) -> Tuple[str, int]:
    """
    Runs a program, returning status and accumulator.

    The status can be either "loop" or "halt".
    """
    pc = 0
    acc = 0
    instructions_run = set()
    while True:
        if pc == len(code):
            return "halt", acc
        if pc in instructions_run:
            return "loop", acc
        instructions_run.add(pc)
        op, n = code[pc]
        if op == "acc":
            acc += n
            pc += 1
        elif op == "nop":
            pc += 1
        elif op == "jmp":
            pc += n
        else:
            raise Exception("bad op code: " + op)