import struct
RC=[0x0000000000000001,0x0000000000008082,0x800000000000808a,0x8000000080008000,
0x000000000000808b,0x0000000080000001,0x8000000080008081,0x8000000000008009,
0x000000000000008a,0x0000000000000088,0x0000000080008009,0x000000008000000a,
0x000000008000808b,0x800000000000008b,0x8000000000008089,0x8000000000008003,
0x8000000000008002,0x8000000000000080,0x000000000000800a,0x800000008000000a,
0x8000000080008081,0x8000000000008080,0x0000000080000001,0x8000000080008008]
R=[[0,36,3,41,18],[1,44,10,45,2],[62,6,43,15,61],[28,55,25,21,56],[27,20,39,8,14]]
M=(1<<64)-1
def rol(x,n): n%=64; return ((x<<n)|(x>>(64-n)))&M
def f1600(A):
    for rnd in range(24):
        C=[A[x]^A[x+5]^A[x+10]^A[x+15]^A[x+20] for x in range(5)]
        D=[C[(x+4)%5]^rol(C[(x+1)%5],1) for x in range(5)]
        for x in range(5):
            for y in range(5): A[x+5*y]^=D[x]
        B=[0]*25
        for x in range(5):
            for y in range(5): B[y+5*((2*x+3*y)%5)]=rol(A[x+5*y],R[x][y])
        for x in range(5):
            for y in range(5): A[x+5*y]=B[x+5*y]^((~B[(x+1)%5+5*y])&M)&B[(x+2)%5+5*y]
        A[0]^=RC[rnd]
    return A
POW_INIT=[1242148031264380989,3008272977830772284,2188519011337848018,1992179434288343456,8876506674959887717,
5399642050693751366,1745875063082670864,8605242046444978844,17936695144567157056,3343109343542796272,
1123092876221303306,4963925045340115282,17037383077651887893,16629644495023626889,12833675776649114147,
3784524041015224902,1082795874807940378,13952716920571277634,13411128033953605860,15060696040649351053,
9928834659948351306,5237849264682708699,12825353012139217522,6706187291358897596,196324915476054915]
HEAVY_INIT=[4239941492252378377,8746723911537738262,8796936657246353646,1272090201925444760,16654558671554924250,
8270816933120786537,13907396207649043898,6782861118970774626,9239690602118867528,11582319943599406348,
17596056728278508070,15212962468105129023,7812475424661425213,3370482334374859748,5690099369266491460,
8596393687355028144,570094237299545110,9119540418498120711,16901969272480492857,13372017233735502424,
14372891883993151831,5171152063242093102,10573107899694386186,6096431547456407061,1592359455985097269]
le4=lambda b: list(struct.unpack('<4Q',b))
frm=lambda w: struct.pack('<4Q',*[x&M for x in w])
def pow_hash(pre,ts,nonce):
    s=list(POW_INIT)
    for i,w in enumerate(le4(pre)): s[i]^=w
    s[4]^=ts&M; s[9]^=nonce&M
    return frm(f1600(s)[:4])
def heavy(h):
    s=list(HEAVY_INIT)
    for i,w in enumerate(le4(h)): s[i]^=w
    return frm(f1600(s)[:4])
class Xo:
    def __init__(s,h): s.s=le4(h)
    def u64(s):
        s0,s1,s2,s3=s.s
        res=(s0+rol((s0+s3)&M,23))&M
        t=(s1<<17)&M
        s2^=s0; s3^=s1; s1^=s2; s0^=s3; s2^=t; s3=rol(s3,45)
        s.s=[s0,s1,s2,s3]; return res
def rank64(m):
    f=[[float(v) for v in row] for row in m]; rank=0; sel=[False]*64
    for i in range(64):
        j=0
        while j<64:
            if not sel[j] and abs(f[j][i])>1e-9: break
            j+=1
        if j!=64:
            rank+=1; sel[j]=True
            for p in range(i+1,64): f[j][p]/=f[j][i]
            for k in range(64):
                if k!=j and abs(f[k][i])>1e-9:
                    for p in range(i+1,64): f[k][p]-=f[j][p]*f[k][i]
    return rank
def gen_matrix(pre):
    g=Xo(pre)
    while True:
        m=[]
        for _ in range(64):
            row=[]; val=0
            for j in range(64):
                sh=j%16
                if sh==0: val=g.u64()
                row.append((val>>(4*sh))&0xF)
            m.append(row)
        if rank64(m)==64: return m
def heavy_hash(m,h):
    v=[]
    for b in h: v.append(b>>4); v.append(b&0xF)
    prod=bytearray(32)
    for i in range(32):
        s1=0; s2=0
        for j in range(64):
            s1=(s1+m[2*i][j]*v[j])&0xFFFF
            s2=(s2+m[2*i+1][j]*v[j])&0xFFFF
        prod[i]=(((s1>>10)<<4)|(s2>>10))&0xFF
    for i in range(32): prod[i]^=h[i]
    return heavy(bytes(prod))
def target_from_bits(bits):
    exp=bits>>24; mant=bits&0x007fffff
    return mant*(1<<(8*(exp-3))) if exp>3 else mant>>(8*(3-exp))