lines = [int(line) for line in open("20.input")]

def show(nxt):
    start = 0
    current = start
    while True:
        print(lines[current], " ", end="")
        current = nxt[current]
        if current == start:
            break

    print("")

full_circ = len(lines) - 1

def mix(lines, repeat=1):
    nxt = {i: i+1 for i in range(len(lines)-1)}
    nxt[len(lines)-1] = 0

    prev = {v: k for k, v in nxt.items()}

    for i in range(repeat):
        print("Iteration", i + 1)
        for num, val in enumerate(lines):
            if val > 0:
                target = num
                for i in range(val % full_circ):
                    target = nxt[target]
                if target == num:
                    continue

                nxt[prev[num]] = nxt[num]

                tmp_nxt = nxt[target]
                nxt[target] = num
                nxt[num] = tmp_nxt

                prev = {v: k for k, v in nxt.items()}

            elif val < 0:
                target = num
                for i in range((-val) % full_circ):
                    target = prev[target]
                if target == num:
                    continue

                prev[nxt[num]] = prev[num]

                tmp_prev = prev[target]
                prev[target] = num
                prev[num] = tmp_prev

                nxt = {v: k for k, v in prev.items()}

            #show(nxt)

    total = 0

    current = max(i for i, v in enumerate(lines) if v == 0)
    for i in range(1, 3001):
        current = nxt[current]
        if i % 1000 == 0:
            total += lines[current]

    return total

print("Part 1:", mix(lines, 1))
print("Part 2:", mix([811589153 * x for x in lines], 10))