import random
import requests
import subprocess
import sys
import time

# MT19937 constants
W, N, M, R = 32, 624, 397, 31
A = 0x9908B0DF

w_upper = (1 << W) - (1 << R)
w_lower = (1 << R) - (1 << 0)
w_full = (1 << W) - (1 << 0)

def _mask_lower(n):
    return (1 << n) - (1 << 0)

def mask_lower(bits, n, shl):
    mask = _mask_lower(n)
    return (bits & mask) << shl

def _mask_upper(n):
    return (1 << W) - (1 << (W - n))

def mask_upper(bits, n, shr):
    mask = _mask_upper(n)
    return (bits & mask) >> shr

def undo_selfxor(bits, mask, shr, shl):
    dirty = (mask << shl) >> shr
    clean = w_full ^ dirty
    assert(dirty == (dirty & w_full))
    rec = bits & clean
    while dirty != 0:
        pre = clean & ((dirty << shr) >> shl)
        post = ((pre << shl) >> shr) & w_full
        assert(pre != 0) # we can recover new bits
        rec |= (((rec & pre) << shl) >> shr) ^ (bits & post)
        clean |= post
        dirty &= w_full ^ clean
    return rec

def harden(bits):
    bits ^= mask_upper(bits, W - 11, 11)
    bits ^= mask_lower(bits, W -  7,  7) & 0x9d2c5680
    bits ^= mask_lower(bits, W - 15, 15) & 0xefc60000
    bits ^= mask_upper(bits, W - 18, 18)
    return bits

def unharden(bits):
    bits = undo_selfxor(bits, _mask_upper(W - 18), 18, 0)
    bits = undo_selfxor(bits, _mask_lower(W - 15) & (0xefc60000 >> 15), 0, 15)
    bits = undo_selfxor(bits, _mask_lower(W - 7) & (0x9d2c5680 >> 7), 0, 7)
    bits = undo_selfxor(bits, _mask_upper(W - 11), 11, 0)
    return bits

val = random.getrandbits(32)
assert(unharden(harden(val)) == val)

# for initial state population from seed
def mutate(state_in, out_i):
    return (1812433253 * (state_in ^ (state_in >> 30)) + out_i) & w_full

def unmutate(state_out, out_i):
    state_sub = (state_out + (1 << W) - out_i) & w_full
    state_xor = (2520285293 * state_sub) & w_full
    return undo_selfxor(state_xor, _mask_upper(2), 30, 0)

val = random.getrandbits(32)
assert(unmutate(mutate(val, 1), 1) == val)

def mul_a(x):
    return (x >> 1) ^ (A * (x & 1))

def twist(m, u, v):
    ax = mul_a((u & w_upper) | (v & w_lower))
    return m ^ ax

def from_ax(ax):
    if ax & (1 << 31):
        assert((ax ^ A) & w_full == (ax ^ A))
        x = ((ax ^ A) << 1) | 1
    else:
        x = ax << 1
    return x

def gen_next(states):
    si = len(states)
    ax = mul_a(states[si - N][1] | states[si - N + 1][0])
    return states[si - N + M][2] ^ ax

def untwist_m_n(m, n):
    x = from_ax(m ^ n)
    return x & w_upper, x & w_lower

def consolidate_from_full(state):
    if state[2] is not None:
        state[0] = state[2] & w_lower
        state[1] = state[2] & w_upper

def consolidate_to_full(state):
    if state[0] is not None and state[1] is not None:
        state[2] = state[0] | state[1]

def php_reload(states):
    for i in range(N - M):
        states[i][2] = twist(states[i+M][2], states[i][2], states[i+1][2])
    for i in range(N - M, N - 1):
        states[i][2] = twist(states[i-N+M][2], states[i][2], states[i+1][2])
    states[N-1][2] = twist(states[M][2], states[N-1][2], states[0][2])
    for state in states:
        consolidate_from_full(state)

def php_srand(val):
    inner = [[None, None, None] for _ in range(N)]
    inner[0][2] = val
    consolidate_from_full(inner[0])
    for i in range(1, N):
        inner[i][2] = mutate(inner[i-1][2], i)
        consolidate_from_full(inner[i])
    states = [s[:] for s in inner]
    php_reload(states)
    return inner, states

# |A                |B               |
# 0              N - M               N
P_A, P_B = (0, N - M)

#   states[B] = twist(states[B + M - N], _states[B], _states[B+1]
#             = twist(states[N - M + M - N], _states[B], _states[B+1])
#             = twist(states[0], _states[B], _states[B+1])
#             = twist(states[A], _states[B], _states[B+1]) => can recover _state[B+1]

def recover(sa, sb):
    initial = [[None, None, None] for _ in range(N)]
    initial[P_B][1], initial[P_B+1][0] = untwist_m_n(sa, sb)

    # recover upper bit
    cands = []
    for b in (0, 1):
        initial[P_B+1][1] = b << 31
        consolidate_to_full(initial[P_B+1])
        initial[P_B][2] = unmutate(initial[P_B+1][2], P_B+1)
        if initial[P_B][1] == initial[P_B][2] & w_upper:
            cands.append(b)
    if len(cands) != 1:
        return

    initial[P_B+1][1] = cands[0] << 31
    consolidate_to_full(initial[P_B+1])

    for i in range(P_B+2, N, 1):
        initial[i][2] = mutate(initial[i-1][2], i);
        consolidate_from_full(initial[i])

    for i in range(P_B, -1, -1):
        initial[i][2] = unmutate(initial[i+1][2], i+1)
        consolidate_from_full(initial[i])

    prediction = gen_next(initial)
    expectation = sa

    if prediction == expectation:
        return initial
    return None

def main(host="localhost:9095"):
    print("Timing request..", end="", flush=True)
    while True:
        s = int(time.time()) % 60
        if s == 46:
            break
        print(".", end="", flush=True)
        time.sleep(1)
    print()

    session = requests.Session()

    r = session.get(f"http://{host}")
    values = [int(v) for v in r.text.split("\n")[:-2]]
    stime, sa_h, sb_h = values[0], values[1], values[2+3]
    assert(stime % 60 == 46) # 3 * 60 + 47 = 227 (but off-by-one)

    # initial, states = php_srand(0)
    # sa_h = harden(states[0]) >> 1
    # sb_h = harden(states[N-M]) >> 1

    nextv = None
    for bits in range(1 << 2):
        sa = unharden((sa_h << 1) | ((bits >> 0) & 1))
        sb = unharden((sb_h << 1) | ((bits >> 1) & 1))
        if initial := recover(sa, sb):
            print("FOUND")
            php_reload(initial)
            nextv = harden(initial[301][2]) >> 1
            break
    assert(nextv is not None)

    r = session.post(f"http://{host}/submit", data={"next": nextv})
    print(r.text)

if __name__ == "__main__":
    main(*sys.argv[1:])