from timeit import default_timer as timer

s = open("inputs/16.txt").read().strip()
pattern = [0, 1, 0, -1]


def solve(message, offset, repeat):
    v = list(map(int, s)) * repeat
    N = len(v)
    v2 = [0] * N
    cumsum = [0] * (N + 1)
    for phase in range(100):
        ts = timer()
        # Precompute cumulative sums in O(N) so we can do fast range sums
        cumsum[0] = 0
        for i in range(N):
            cumsum[i + 1] = cumsum[i] + v[i]
        # Each entry sums intervals with increasing width. Inner loop takes O(N/w) so
        # O(N / 1 + N / 2 + N / 3 + ... + N / N) which is O(N*H_N) or O(N*log(N))
        for i in range(N):
            total = 0
            w = i + 1
            # Sum intervals of width w (special casing the first and last interval)
            p = 0
            for j in range(-1, N, w):
                start = j
                if start < 0:
                    start = 0
                end = j + w
                if end >= N + 1:
                    end = N
                total += pattern[p] * (cumsum[end] - cumsum[start])
                p = (p + 1) % 4
            v2[i] = abs(total) % 10

        v, v2 = v2, v
        ts2 = timer()
        print(phase, ts2 - ts)

    print(message, "".join(map(str, v[offset : offset + 8])))


solve("Part1", 0, 1)
solve("Part2", s[:7], 10000)