# THE IGNITION QUESTION: why do two consecutive C's form for k<=8 and
# not at k=9? Anatomy of every seed, by contact.
N = 1 << 13
Q = [0,1,1] + [0]*(N-2)
for n in range(3, N+1):
    Q[n] = Q[n-Q[n-1]] + Q[n-Q[n-2]]

def plateau_span(k):
    m = 3*(1<<k); C = m//2
    s = m
    while s > 1 and Q[s-1] == C: s -= 1
    return s, m, C   # plateau is [s, m-1] valued C (empty if s==m)

print("=== SEED ANATOMY, k=2..9 ===")
spans = {}
for k in range(2, 10):
    s, m, C = plateau_span(k)
    spans[k] = (s, m, C)
for k in range(3, 10):
    s, m, C = spans[k]
    ps, pm, pC = spans[k-1]           # previous plateau: fuel, value C/2
    print("\nk=%d  midpoint=%d  C=%d  plateau=[%d..%d] len=%d   fuel=[%d..%d] val=%d len=%d" % (
        k, m, C, s, m-1, m-s, ps, pm-1, pC, pm-ps))
    lo = s-4 if s < m else m-6
    for n in range(lo, min(s+2, m)):
        a = n - Q[n-1]; b = n - Q[n-2]
        in_fuel_a = ps <= a <= pm-1
        in_fuel_b = ps <= b <= pm-1
        tag = "SEED" if (s < m and n in (s, s+1)) else "    "
        print("  %s n=%-5d Q=%-5d pred=(%d,%d) addr=(%d,%d) summands=(%d,%d) fuel-hit=(%s,%s)" % (
            tag, n, Q[n], Q[n-1], Q[n-2], a, b, Q[a], Q[b],
            "Y" if in_fuel_a else "n", "Y" if in_fuel_b else "n"))

print("\n=== THE RACE: window vs weather ===")
print(" k   window(fuel len)   aim errors |Q-C| on 4 cells before seed/midpoint")
for k in range(3, 10):
    s, m, C = spans[k]
    ref = s if s < m else m
    errs = [abs(Q[n]-C) for n in range(ref-4, ref)]
    ps, pm, pC = spans[k-1]
    print("  %d      %d               %s" % (k, pm-ps, errs))

print("\n=== does ignition EVER recover? longest exact-C run near later midpoints ===")
for k in range(9, 12):
    m = 3*(1<<k); C = m//2
    if m > N: break
    best = 0; cur = 0
    for n in range(m-200, m+1):
        if Q[n] == C: cur += 1; best = max(best, cur)
        else: cur = 0
    print("  k=%d midpoint=%d: longest run of exact C within 200 before midpoint = %d" % (k, m, best))