from array import array
import sys
cq=30
g=(1<<cq)-1
cb=(1<<15)-1
def b9():
    bk=list(map(int,sys.stdin.buffer.read().split()))
    i=0
    n=bk[0]
    m=bk[1]
    i=2
    aX=array("I",bk[i:i+n])
    i+=n
    bP=[]
    for _ in range(5):
        bR=array("I",[0])
        bR.extend(bk[i:i+m])
        bP.append(bR)
        i+=m
    aC=bk[i]
    i+=1
    bx=array("I",[0])*aC
    cg=array("I",[0])*aC
    for k in range(aC):
        bx[k]=bk[i]
        cg[k]=bk[i+1]
        i+=2
    return(n,m,aX,bP[0],bP[1],bP[2],bP[3],bP[4],aC,bx,cg)
def b_(bk):
    n=len(bk)
    aU=1
    while aU<n:
        aU<<=1
    bS=aU<<1
    bp=aU.bit_length()-1
    bZ=(n*g+2).bit_length()
    cl=1<<bZ
    cc=cl-1
    J=cl-2
    cd=15*bZ
    bf=[0]*(1<<15)
    G=0
    for cs in range(30):
        G|=1<<(cs*bZ)
    for X in range(1,1<<15):
        bJ=X&-X
        bf[X]=bf[X^bJ]|(cc<<((bJ.bit_length()-1)*bZ))
    b5=[v<<cd for v in bf]
    C=[0]*bS
    q=[0]*bS
    c=[0]*bS
    a=[0]*bS
    o=[g]*bS
    w=[0]*bS
    P=bytearray(bS)
    p=aU
    T=bf
    S=b5
    N=cb
    for aQ in bk:
        C[p]=aQ
        q[p]=(T[aQ&N]|S[aQ>>15])&G
        c[p]=aQ
        a[p]=aQ
        p+=1
    p=aU-1
    while p:
        aa=p<<1
        U=aa|1
        C[p]=C[aa]+C[U]
        q[p]=q[aa]+q[U]
        c[p]=c[aa]|c[U]
        a[p]=a[aa]&a[U]
        p-=1
    bt=C.copy()
    bn=q.copy()
    bH=c.copy()
    bG=a.copy()
    bA=[]
    bl=bA.append
    def V(p,P=P,bl=bl):
        P[p]=1
        bl(p)
    def bb(p,aj,h,j,C=C,q=q,c=c,a=a,o=o,w=w,P=P,V=V,T=T,S=S,G=G,N=N,J=J):
        aa=p<<1
        U=aa|1
        if h==j:
            aI=j
            b2=T[aI&N]|S[aI>>15]
            bB=(b2&G)*aj
            aS=c[aa]
            if aS!=aI or a[aa]!=aI:
                if not P[aa]:
                    V(aa)
                C[aa]=aj*aI
                q[aa]=bB
                c[aa]=aI
                a[aa]=aI
                o[aa]=aI
                w[aa]=aI
            aS=c[U]
            if aS!=aI or a[U]!=aI:
                if not P[U]:
                    V(U)
                C[U]=aj*aI
                q[U]=bB
                c[U]=aI
                a[U]=aI
                o[U]=aI
                w[U]=aI
        elif h==g:
            X=j
            aZ=a[aa]
            I=X&(g^aZ)
            if I:
                if not P[aa]:
                    V(aa)
                B=T[I&N]|S[I>>15]
                bh=B&G
                K=q[aa]
                C[aa]+=aj*I-((K&B)%J)
                q[aa]=(K&~B)|(bh*aj)
                c[aa]|=X
                a[aa]=aZ|X
                o[aa]|=X
                w[aa]|=X
            aZ=a[U]
            I=X&(g^aZ)
            if I:
                if not P[U]:
                    V(U)
                B=T[I&N]|S[I>>15]
                bh=B&G
                K=q[U]
                C[U]+=aj*I-((K&B)%J)
                q[U]=(K&~B)|(bh*aj)
                c[U]|=X
                a[U]=aZ|X
                o[U]|=X
                w[U]|=X
        elif j==0:
            X=h
            aE=g^X
            aS=c[aa]
            I=aS&aE
            if I:
                if not P[aa]:
                    V(aa)
                B=T[I&N]|S[I>>15]
                K=q[aa]
                C[aa]-=(K&B)%J
                q[aa]=K&~B
                c[aa]=aS&X
                a[aa]&=X
                o[aa]&=X
                w[aa]&=X
            aS=c[U]
            I=aS&aE
            if I:
                if not P[U]:
                    V(U)
                B=T[I&N]|S[I>>15]
                K=q[U]
                C[U]-=(K&B)%J
                q[U]=K&~B
                c[U]=aS&X
                a[U]&=X
                o[U]&=X
                w[U]&=X
        else:
            aK=aa
            aS=c[aK]
            aZ=a[aK]
            aD=aS&(g^h)
            ap=j&(g^aZ)
            I=aD|ap
            if I:
                if not P[aK]:
                    V(aK)
                bV=T[ap&N]|S[ap>>15]
                bU=bV&G
                B=T[I&N]|S[I>>15]
                K=q[aK]
                C[aK]+=aj*ap-((K&B)%J)
                q[aK]=(K&~B)|(bU*aj)
                c[aK]=(aS&h)|j
                a[aK]=(aZ&h)|j
                o[aK]=(o[aK]&h)|j
                w[aK]=(w[aK]&h)|j
            aK=U
            aS=c[aK]
            aZ=a[aK]
            aD=aS&(g^h)
            ap=j&(g^aZ)
            I=aD|ap
            if I:
                if not P[aK]:
                    V(aK)
                bV=T[ap&N]|S[ap>>15]
                bU=bV&G
                B=T[I&N]|S[I>>15]
                K=q[aK]
                C[aK]+=aj*ap-((K&B)%J)
                q[aK]=(K&~B)|(bU*aj)
                c[aK]=(aS&h)|j
                a[aK]=(aZ&h)|j
                o[aK]=(o[aK]&h)|j
                w[aK]=(w[aK]&h)|j
        o[p]=g
        w[p]=0
    W=[0]*((aU.bit_length()<<2)+4)
    def a_(aB,ax,X,C=C,q=q,c=c,a=a,o=o,w=w,P=P,V=V,bb=bb,T=T,S=S,G=G,N=N,aU=aU,W=W):
        aE=g^X
        if not aE:
            return
        Q=0
        p=1
        ab=0
        ar=aU
        while True:
            I=c[p]&aE
            if not I:
                break
            if aB<=ab and ab+ar<=ax:
                if not P[p]:
                    V(p)
                B=T[I&N]|S[I>>15]
                K=q[p]
                C[p]-=(K&B)%J
                q[p]=K&~B
                c[p]&=X
                a[p]&=X
                o[p]&=X
                w[p]&=X
                break
            aj=ar>>1
            h=o[p]
            j=w[p]
            if h!=g or j:
                t=p<<1
                l=t|1
                if h==j:
                    s=j
                    aq=T[s&N]|S[s>>15]
                    Y=(aq&G)*aj
                    A=c[t]
                    if A!=s or a[t]!=s:
                        if not P[t]:
                            V(t)
                        C[t]=aj*s
                        q[t]=Y
                        c[t]=s
                        a[t]=s
                        o[t]=s
                        w[t]=s
                    A=c[l]
                    if A!=s or a[l]!=s:
                        if not P[l]:
                            V(l)
                        C[l]=aj*s
                        q[l]=Y
                        c[l]=s
                        a[l]=s
                        o[l]=s
                        w[l]=s
                elif h==g:
                    E=j
                    F=a[t]
                    e=E&(g^F)
                    if e:
                        if not P[t]:
                            V(t)
                        d=T[e&N]|S[e>>15]
                        aG=d&G
                        f=q[t]
                        C[t]+=aj*e-((f&d)%J)
                        q[t]=(f&~d)|(aG*aj)
                        c[t]|=E
                        a[t]=F|E
                        o[t]|=E
                        w[t]|=E
                    F=a[l]
                    e=E&(g^F)
                    if e:
                        if not P[l]:
                            V(l)
                        d=T[e&N]|S[e>>15]
                        aG=d&G
                        f=q[l]
                        C[l]+=aj*e-((f&d)%J)
                        q[l]=(f&~d)|(aG*aj)
                        c[l]|=E
                        a[l]=F|E
                        o[l]|=E
                        w[l]|=E
                elif j==0:
                    E=h
                    am=g^E
                    A=c[t]
                    e=A&am
                    if e:
                        if not P[t]:
                            V(t)
                        d=T[e&N]|S[e>>15]
                        f=q[t]
                        C[t]-=(f&d)%J
                        q[t]=f&~d
                        c[t]=A&E
                        a[t]&=E
                        o[t]&=E
                        w[t]&=E
                    A=c[l]
                    e=A&am
                    if e:
                        if not P[l]:
                            V(l)
                        d=T[e&N]|S[e>>15]
                        f=q[l]
                        C[l]-=(f&d)%J
                        q[l]=f&~d
                        c[l]=A&E
                        a[l]&=E
                        o[l]&=E
                        w[l]&=E
                else:
                    r=t
                    A=c[r]
                    F=a[r]
                    ac=A&(g^h)
                    H=j&(g^F)
                    e=ac|H
                    if e:
                        if not P[r]:
                            V(r)
                        ag=T[H&N]|S[H>>15]
                        af=ag&G
                        d=T[e&N]|S[e>>15]
                        f=q[r]
                        C[r]+=aj*H-((f&d)%J)
                        q[r]=(f&~d)|(af*aj)
                        c[r]=(A&h)|j
                        a[r]=(F&h)|j
                        o[r]=(o[r]&h)|j
                        w[r]=(w[r]&h)|j
                    r=l
                    A=c[r]
                    F=a[r]
                    ac=A&(g^h)
                    H=j&(g^F)
                    e=ac|H
                    if e:
                        if not P[r]:
                            V(r)
                        ag=T[H&N]|S[H>>15]
                        af=ag&G
                        d=T[e&N]|S[e>>15]
                        f=q[r]
                        C[r]+=aj*H-((f&d)%J)
                        q[r]=(f&~d)|(af*aj)
                        c[r]=(A&h)|j
                        a[r]=(F&h)|j
                        o[r]=(o[r]&h)|j
                        w[r]=(w[r]&h)|j
                o[p]=g
                w[p]=0
            W[Q]=p
            Q+=1
            aH=ab+aj
            if ax<=aH:
                p<<=1
                ar=aj
                continue
            if aB>=aH:
                p=p<<1|1
                ab=aH
                ar=aj
                continue
            D=p<<1
            ad=ab
            L=aj
            while True:
                I=c[D]&aE
                if not I:
                    break
                if aB<=ad:
                    if not P[D]:
                        V(D)
                    B=T[I&N]|S[I>>15]
                    K=q[D]
                    C[D]-=(K&B)%J
                    q[D]=K&~B
                    c[D]&=X
                    a[D]&=X
                    o[D]&=X
                    w[D]&=X
                    break
                x=L>>1
                h=o[D]
                j=w[D]
                if h!=g or j:
                    t=D<<1
                    l=t|1
                    if h==j:
                        s=j
                        aq=T[s&N]|S[s>>15]
                        Y=(aq&G)*x
                        A=c[t]
                        if A!=s or a[t]!=s:
                            if not P[t]:
                                V(t)
                            C[t]=x*s
                            q[t]=Y
                            c[t]=s
                            a[t]=s
                            o[t]=s
                            w[t]=s
                        A=c[l]
                        if A!=s or a[l]!=s:
                            if not P[l]:
                                V(l)
                            C[l]=x*s
                            q[l]=Y
                            c[l]=s
                            a[l]=s
                            o[l]=s
                            w[l]=s
                    elif h==g:
                        E=j
                        F=a[t]
                        e=E&(g^F)
                        if e:
                            if not P[t]:
                                V(t)
                            d=T[e&N]|S[e>>15]
                            aG=d&G
                            f=q[t]
                            C[t]+=x*e-((f&d)%J)
                            q[t]=(f&~d)|(aG*x)
                            c[t]|=E
                            a[t]=F|E
                            o[t]|=E
                            w[t]|=E
                        F=a[l]
                        e=E&(g^F)
                        if e:
                            if not P[l]:
                                V(l)
                            d=T[e&N]|S[e>>15]
                            aG=d&G
                            f=q[l]
                            C[l]+=x*e-((f&d)%J)
                            q[l]=(f&~d)|(aG*x)
                            c[l]|=E
                            a[l]=F|E
                            o[l]|=E
                            w[l]|=E
                    elif j==0:
                        E=h
                        am=g^E
                        A=c[t]
                        e=A&am
                        if e:
                            if not P[t]:
                                V(t)
                            d=T[e&N]|S[e>>15]
                            f=q[t]
                            C[t]-=(f&d)%J
                            q[t]=f&~d
                            c[t]=A&E
                            a[t]&=E
                            o[t]&=E
                            w[t]&=E
                        A=c[l]
                        e=A&am
                        if e:
                            if not P[l]:
                                V(l)
                            d=T[e&N]|S[e>>15]
                            f=q[l]
                            C[l]-=(f&d)%J
                            q[l]=f&~d
                            c[l]=A&E
                            a[l]&=E
                            o[l]&=E
                            w[l]&=E
                    else:
                        r=t
                        A=c[r]
                        F=a[r]
                        ac=A&(g^h)
                        H=j&(g^F)
                        e=ac|H
                        if e:
                            if not P[r]:
                                V(r)
                            ag=T[H&N]|S[H>>15]
                            af=ag&G
                            d=T[e&N]|S[e>>15]
                            f=q[r]
                            C[r]+=x*H-((f&d)%J)
                            q[r]=(f&~d)|(af*x)
                            c[r]=(A&h)|j
                            a[r]=(F&h)|j
                            o[r]=(o[r]&h)|j
                            w[r]=(w[r]&h)|j
                        r=l
                        A=c[r]
                        F=a[r]
                        ac=A&(g^h)
                        H=j&(g^F)
                        e=ac|H
                        if e:
                            if not P[r]:
                                V(r)
                            ag=T[H&N]|S[H>>15]
                            af=ag&G
                            d=T[e&N]|S[e>>15]
                            f=q[r]
                            C[r]+=x*H-((f&d)%J)
                            q[r]=(f&~d)|(af*x)
                            c[r]=(A&h)|j
                            a[r]=(F&h)|j
                            o[r]=(o[r]&h)|j
                            w[r]=(w[r]&h)|j
                    o[D]=g
                    w[D]=0
                W[Q]=D
                Q+=1
                ah=ad+x
                if aB>=ah:
                    D=D<<1|1
                    ad=ah
                    L=x
                else:
                    R=D<<1|1
                    Z=c[R]&aE
                    if Z:
                        if not P[R]:
                            V(R)
                        B=T[Z&N]|S[Z>>15]
                        K=q[R]
                        C[R]-=(K&B)%J
                        q[R]=K&~B
                        c[R]&=X
                        a[R]&=X
                        o[R]&=X
                        w[R]&=X
                    D<<=1
                    L=x
            D=p<<1|1
            ad=aH
            L=aj
            while True:
                I=c[D]&aE
                if not I:
                    break
                if ad+L<=ax:
                    if not P[D]:
                        V(D)
                    B=T[I&N]|S[I>>15]
                    K=q[D]
                    C[D]-=(K&B)%J
                    q[D]=K&~B
                    c[D]&=X
                    a[D]&=X
                    o[D]&=X
                    w[D]&=X
                    break
                x=L>>1
                h=o[D]
                j=w[D]
                if h!=g or j:
                    t=D<<1
                    l=t|1
                    if h==j:
                        s=j
                        aq=T[s&N]|S[s>>15]
                        Y=(aq&G)*x
                        A=c[t]
                        if A!=s or a[t]!=s:
                            if not P[t]:
                                V(t)
                            C[t]=x*s
                            q[t]=Y
                            c[t]=s
                            a[t]=s
                            o[t]=s
                            w[t]=s
                        A=c[l]
                        if A!=s or a[l]!=s:
                            if not P[l]:
                                V(l)
                            C[l]=x*s
                            q[l]=Y
                            c[l]=s
                            a[l]=s
                            o[l]=s
                            w[l]=s
                    elif h==g:
                        E=j
                        F=a[t]
                        e=E&(g^F)
                        if e:
                            if not P[t]:
                                V(t)
                            d=T[e&N]|S[e>>15]
                            aG=d&G
                            f=q[t]
                            C[t]+=x*e-((f&d)%J)
                            q[t]=(f&~d)|(aG*x)
                            c[t]|=E
                            a[t]=F|E
                            o[t]|=E
                            w[t]|=E
                        F=a[l]
                        e=E&(g^F)
                        if e:
                            if not P[l]:
                                V(l)
                            d=T[e&N]|S[e>>15]
                            aG=d&G
                            f=q[l]
                            C[l]+=x*e-((f&d)%J)
                            q[l]=(f&~d)|(aG*x)
                            c[l]|=E
                            a[l]=F|E
                            o[l]|=E
                            w[l]|=E
                    elif j==0:
                        E=h
                        am=g^E
                        A=c[t]
                        e=A&am
                        if e:
                            if not P[t]:
                                V(t)
                            d=T[e&N]|S[e>>15]
                            f=q[t]
                            C[t]-=(f&d)%J
                            q[t]=f&~d
                            c[t]=A&E
                            a[t]&=E
                            o[t]&=E
                            w[t]&=E
                        A=c[l]
                        e=A&am
                        if e:
                            if not P[l]:
                                V(l)
                            d=T[e&N]|S[e>>15]
                            f=q[l]
                            C[l]-=(f&d)%J
                            q[l]=f&~d
                            c[l]=A&E
                            a[l]&=E
                            o[l]&=E
                            w[l]&=E
                    else:
                        r=t
                        A=c[r]
                        F=a[r]
                        ac=A&(g^h)
                        H=j&(g^F)
                        e=ac|H
                        if e:
                            if not P[r]:
                                V(r)
                            ag=T[H&N]|S[H>>15]
                            af=ag&G
                            d=T[e&N]|S[e>>15]
                            f=q[r]
                            C[r]+=x*H-((f&d)%J)
                            q[r]=(f&~d)|(af*x)
                            c[r]=(A&h)|j
                            a[r]=(F&h)|j
                            o[r]=(o[r]&h)|j
                            w[r]=(w[r]&h)|j
                        r=l
                        A=c[r]
                        F=a[r]
                        ac=A&(g^h)
                        H=j&(g^F)
                        e=ac|H
                        if e:
                            if not P[r]:
                                V(r)
                            ag=T[H&N]|S[H>>15]
                            af=ag&G
                            d=T[e&N]|S[e>>15]
                            f=q[r]
                            C[r]+=x*H-((f&d)%J)
                            q[r]=(f&~d)|(af*x)
                            c[r]=(A&h)|j
                            a[r]=(F&h)|j
                            o[r]=(o[r]&h)|j
                            w[r]=(w[r]&h)|j
                    o[D]=g
                    w[D]=0
                W[Q]=D
                Q+=1
                ah=ad+x
                if ax<=ah:
                    D<<=1
                    L=x
                else:
                    R=D<<1
                    Z=c[R]&aE
                    if Z:
                        if not P[R]:
                            V(R)
                        B=T[Z&N]|S[Z>>15]
                        K=q[R]
                        C[R]-=(K&B)%J
                        q[R]=K&~B
                        c[R]&=X
                        a[R]&=X
                        o[R]&=X
                        w[R]&=X
                    D=D<<1|1
                    ad=ah
                    L=x
            break
        while Q:
            Q-=1
            p=W[Q]
            aa=p<<1
            U=aa|1
            bs=C[aa]+C[U]
            if bs!=C[p]:
                if not P[p]:
                    V(p)
                C[p]=bs
                q[p]=q[aa]+q[U]
                c[p]=c[aa]|c[U]
                a[p]=a[aa]&a[U]
    def a8(aB,ax,X,C=C,q=q,c=c,a=a,o=o,w=w,P=P,V=V,bb=bb,T=T,S=S,G=G,N=N,aU=aU,W=W):
        if not X:
            return
        Q=0
        p=1
        ab=0
        ar=aU
        while True:
            I=X&(g^a[p])
            if not I:
                break
            if aB<=ab and ab+ar<=ax:
                if not P[p]:
                    V(p)
                B=T[I&N]|S[I>>15]
                bh=B&G
                K=q[p]
                C[p]+=ar*I-((K&B)%J)
                q[p]=(K&~B)|(bh*ar)
                c[p]|=X
                a[p]|=X
                o[p]|=X
                w[p]|=X
                break
            aj=ar>>1
            h=o[p]
            j=w[p]
            if h!=g or j:
                t=p<<1
                l=t|1
                if h==j:
                    s=j
                    aq=T[s&N]|S[s>>15]
                    Y=(aq&G)*aj
                    A=c[t]
                    if A!=s or a[t]!=s:
                        if not P[t]:
                            V(t)
                        C[t]=aj*s
                        q[t]=Y
                        c[t]=s
                        a[t]=s
                        o[t]=s
                        w[t]=s
                    A=c[l]
                    if A!=s or a[l]!=s:
                        if not P[l]:
                            V(l)
                        C[l]=aj*s
                        q[l]=Y
                        c[l]=s
                        a[l]=s
                        o[l]=s
                        w[l]=s
                elif h==g:
                    E=j
                    F=a[t]
                    e=E&(g^F)
                    if e:
                        if not P[t]:
                            V(t)
                        d=T[e&N]|S[e>>15]
                        aG=d&G
                        f=q[t]
                        C[t]+=aj*e-((f&d)%J)
                        q[t]=(f&~d)|(aG*aj)
                        c[t]|=E
                        a[t]=F|E
                        o[t]|=E
                        w[t]|=E
                    F=a[l]
                    e=E&(g^F)
                    if e:
                        if not P[l]:
                            V(l)
                        d=T[e&N]|S[e>>15]
                        aG=d&G
                        f=q[l]
                        C[l]+=aj*e-((f&d)%J)
                        q[l]=(f&~d)|(aG*aj)
                        c[l]|=E
                        a[l]=F|E
                        o[l]|=E
                        w[l]|=E
                elif j==0:
                    E=h
                    am=g^E
                    A=c[t]
                    e=A&am
                    if e:
                        if not P[t]:
                            V(t)
                        d=T[e&N]|S[e>>15]
                        f=q[t]
                        C[t]-=(f&d)%J
                        q[t]=f&~d
                        c[t]=A&E
                        a[t]&=E
                        o[t]&=E
                        w[t]&=E
                    A=c[l]
                    e=A&am
                    if e:
                        if not P[l]:
                            V(l)
                        d=T[e&N]|S[e>>15]
                        f=q[l]
                        C[l]-=(f&d)%J
                        q[l]=f&~d
                        c[l]=A&E
                        a[l]&=E
                        o[l]&=E
                        w[l]&=E
                else:
                    r=t
                    A=c[r]
                    F=a[r]
                    ac=A&(g^h)
                    H=j&(g^F)
                    e=ac|H
                    if e:
                        if not P[r]:
                            V(r)
                        ag=T[H&N]|S[H>>15]
                        af=ag&G
                        d=T[e&N]|S[e>>15]
                        f=q[r]
                        C[r]+=aj*H-((f&d)%J)
                        q[r]=(f&~d)|(af*aj)
                        c[r]=(A&h)|j
                        a[r]=(F&h)|j
                        o[r]=(o[r]&h)|j
                        w[r]=(w[r]&h)|j
                    r=l
                    A=c[r]
                    F=a[r]
                    ac=A&(g^h)
                    H=j&(g^F)
                    e=ac|H
                    if e:
                        if not P[r]:
                            V(r)
                        ag=T[H&N]|S[H>>15]
                        af=ag&G
                        d=T[e&N]|S[e>>15]
                        f=q[r]
                        C[r]+=aj*H-((f&d)%J)
                        q[r]=(f&~d)|(af*aj)
                        c[r]=(A&h)|j
                        a[r]=(F&h)|j
                        o[r]=(o[r]&h)|j
                        w[r]=(w[r]&h)|j
                o[p]=g
                w[p]=0
            W[Q]=p
            Q+=1
            aH=ab+aj
            if ax<=aH:
                p<<=1
                ar=aj
                continue
            if aB>=aH:
                p=p<<1|1
                ab=aH
                ar=aj
                continue
            D=p<<1
            ad=ab
            L=aj
            while True:
                I=X&(g^a[D])
                if not I:
                    break
                if aB<=ad:
                    if not P[D]:
                        V(D)
                    B=T[I&N]|S[I>>15]
                    bh=B&G
                    K=q[D]
                    C[D]+=L*I-((K&B)%J)
                    q[D]=(K&~B)|(bh*L)
                    c[D]|=X
                    a[D]|=X
                    o[D]|=X
                    w[D]|=X
                    break
                x=L>>1
                h=o[D]
                j=w[D]
                if h!=g or j:
                    t=D<<1
                    l=t|1
                    if h==j:
                        s=j
                        aq=T[s&N]|S[s>>15]
                        Y=(aq&G)*x
                        A=c[t]
                        if A!=s or a[t]!=s:
                            if not P[t]:
                                V(t)
                            C[t]=x*s
                            q[t]=Y
                            c[t]=s
                            a[t]=s
                            o[t]=s
                            w[t]=s
                        A=c[l]
                        if A!=s or a[l]!=s:
                            if not P[l]:
                                V(l)
                            C[l]=x*s
                            q[l]=Y
                            c[l]=s
                            a[l]=s
                            o[l]=s
                            w[l]=s
                    elif h==g:
                        E=j
                        F=a[t]
                        e=E&(g^F)
                        if e:
                            if not P[t]:
                                V(t)
                            d=T[e&N]|S[e>>15]
                            aG=d&G
                            f=q[t]
                            C[t]+=x*e-((f&d)%J)
                            q[t]=(f&~d)|(aG*x)
                            c[t]|=E
                            a[t]=F|E
                            o[t]|=E
                            w[t]|=E
                        F=a[l]
                        e=E&(g^F)
                        if e:
                            if not P[l]:
                                V(l)
                            d=T[e&N]|S[e>>15]
                            aG=d&G
                            f=q[l]
                            C[l]+=x*e-((f&d)%J)
                            q[l]=(f&~d)|(aG*x)
                            c[l]|=E
                            a[l]=F|E
                            o[l]|=E
                            w[l]|=E
                    elif j==0:
                        E=h
                        am=g^E
                        A=c[t]
                        e=A&am
                        if e:
                            if not P[t]:
                                V(t)
                            d=T[e&N]|S[e>>15]
                            f=q[t]
                            C[t]-=(f&d)%J
                            q[t]=f&~d
                            c[t]=A&E
                            a[t]&=E
                            o[t]&=E
                            w[t]&=E
                        A=c[l]
                        e=A&am
                        if e:
                            if not P[l]:
                                V(l)
                            d=T[e&N]|S[e>>15]
                            f=q[l]
                            C[l]-=(f&d)%J
                            q[l]=f&~d
                            c[l]=A&E
                            a[l]&=E
                            o[l]&=E
                            w[l]&=E
                    else:
                        r=t
                        A=c[r]
                        F=a[r]
                        ac=A&(g^h)
                        H=j&(g^F)
                        e=ac|H
                        if e:
                            if not P[r]:
                                V(r)
                            ag=T[H&N]|S[H>>15]
                            af=ag&G
                            d=T[e&N]|S[e>>15]
                            f=q[r]
                            C[r]+=x*H-((f&d)%J)
                            q[r]=(f&~d)|(af*x)
                            c[r]=(A&h)|j
                            a[r]=(F&h)|j
                            o[r]=(o[r]&h)|j
                            w[r]=(w[r]&h)|j
                        r=l
                        A=c[r]
                        F=a[r]
                        ac=A&(g^h)
                        H=j&(g^F)
                        e=ac|H
                        if e:
                            if not P[r]:
                                V(r)
                            ag=T[H&N]|S[H>>15]
                            af=ag&G
                            d=T[e&N]|S[e>>15]
                            f=q[r]
                            C[r]+=x*H-((f&d)%J)
                            q[r]=(f&~d)|(af*x)
                            c[r]=(A&h)|j
                            a[r]=(F&h)|j
                            o[r]=(o[r]&h)|j
                            w[r]=(w[r]&h)|j
                    o[D]=g
                    w[D]=0
                W[Q]=D
                Q+=1
                ah=ad+x
                if aB>=ah:
                    D=D<<1|1
                    ad=ah
                    L=x
                else:
                    R=D<<1|1
                    Z=X&(g^a[R])
                    if Z:
                        if not P[R]:
                            V(R)
                        B=T[Z&N]|S[Z>>15]
                        bh=B&G
                        K=q[R]
                        C[R]+=x*Z-((K&B)%J)
                        q[R]=(K&~B)|(bh*x)
                        c[R]|=X
                        a[R]|=X
                        o[R]|=X
                        w[R]|=X
                    D<<=1
                    L=x
            D=p<<1|1
            ad=aH
            L=aj
            while True:
                I=X&(g^a[D])
                if not I:
                    break
                if ad+L<=ax:
                    if not P[D]:
                        V(D)
                    B=T[I&N]|S[I>>15]
                    bh=B&G
                    K=q[D]
                    C[D]+=L*I-((K&B)%J)
                    q[D]=(K&~B)|(bh*L)
                    c[D]|=X
                    a[D]|=X
                    o[D]|=X
                    w[D]|=X
                    break
                x=L>>1
                h=o[D]
                j=w[D]
                if h!=g or j:
                    t=D<<1
                    l=t|1
                    if h==j:
                        s=j
                        aq=T[s&N]|S[s>>15]
                        Y=(aq&G)*x
                        A=c[t]
                        if A!=s or a[t]!=s:
                            if not P[t]:
                                V(t)
                            C[t]=x*s
                            q[t]=Y
                            c[t]=s
                            a[t]=s
                            o[t]=s
                            w[t]=s
                        A=c[l]
                        if A!=s or a[l]!=s:
                            if not P[l]:
                                V(l)
                            C[l]=x*s
                            q[l]=Y
                            c[l]=s
                            a[l]=s
                            o[l]=s
                            w[l]=s
                    elif h==g:
                        E=j
                        F=a[t]
                        e=E&(g^F)
                        if e:
                            if not P[t]:
                                V(t)
                            d=T[e&N]|S[e>>15]
                            aG=d&G
                            f=q[t]
                            C[t]+=x*e-((f&d)%J)
                            q[t]=(f&~d)|(aG*x)
                            c[t]|=E
                            a[t]=F|E
                            o[t]|=E
                            w[t]|=E
                        F=a[l]
                        e=E&(g^F)
                        if e:
                            if not P[l]:
                                V(l)
                            d=T[e&N]|S[e>>15]
                            aG=d&G
                            f=q[l]
                            C[l]+=x*e-((f&d)%J)
                            q[l]=(f&~d)|(aG*x)
                            c[l]|=E
                            a[l]=F|E
                            o[l]|=E
                            w[l]|=E
                    elif j==0:
                        E=h
                        am=g^E
                        A=c[t]
                        e=A&am
                        if e:
                            if not P[t]:
                                V(t)
                            d=T[e&N]|S[e>>15]
                            f=q[t]
                            C[t]-=(f&d)%J
                            q[t]=f&~d
                            c[t]=A&E
                            a[t]&=E
                            o[t]&=E
                            w[t]&=E
                        A=c[l]
                        e=A&am
                        if e:
                            if not P[l]:
                                V(l)
                            d=T[e&N]|S[e>>15]
                            f=q[l]
                            C[l]-=(f&d)%J
                            q[l]=f&~d
                            c[l]=A&E
                            a[l]&=E
                            o[l]&=E
                            w[l]&=E
                    else:
                        r=t
                        A=c[r]
                        F=a[r]
                        ac=A&(g^h)
                        H=j&(g^F)
                        e=ac|H
                        if e:
                            if not P[r]:
                                V(r)
                            ag=T[H&N]|S[H>>15]
                            af=ag&G
                            d=T[e&N]|S[e>>15]
                            f=q[r]
                            C[r]+=x*H-((f&d)%J)
                            q[r]=(f&~d)|(af*x)
                            c[r]=(A&h)|j
                            a[r]=(F&h)|j
                            o[r]=(o[r]&h)|j
                            w[r]=(w[r]&h)|j
                        r=l
                        A=c[r]
                        F=a[r]
                        ac=A&(g^h)
                        H=j&(g^F)
                        e=ac|H
                        if e:
                            if not P[r]:
                                V(r)
                            ag=T[H&N]|S[H>>15]
                            af=ag&G
                            d=T[e&N]|S[e>>15]
                            f=q[r]
                            C[r]+=x*H-((f&d)%J)
                            q[r]=(f&~d)|(af*x)
                            c[r]=(A&h)|j
                            a[r]=(F&h)|j
                            o[r]=(o[r]&h)|j
                            w[r]=(w[r]&h)|j
                    o[D]=g
                    w[D]=0
                W[Q]=D
                Q+=1
                ah=ad+x
                if ax<=ah:
                    D<<=1
                    L=x
                else:
                    R=D<<1
                    Z=X&(g^a[R])
                    if Z:
                        if not P[R]:
                            V(R)
                        B=T[Z&N]|S[Z>>15]
                        bh=B&G
                        K=q[R]
                        C[R]+=x*Z-((K&B)%J)
                        q[R]=(K&~B)|(bh*x)
                        c[R]|=X
                        a[R]|=X
                        o[R]|=X
                        w[R]|=X
                    D=D<<1|1
                    ad=ah
                    L=x
            break
        while Q:
            Q-=1
            p=W[Q]
            aa=p<<1
            U=aa|1
            bs=C[aa]+C[U]
            if bs!=C[p]:
                if not P[p]:
                    V(p)
                C[p]=bs
                q[p]=q[aa]+q[U]
                c[p]=c[aa]|c[U]
                a[p]=a[aa]&a[U]
    def cm(aO,X,C=C,q=q,c=c,a=a,o=o,w=w,P=P,V=V,bb=bb,T=T,S=S,N=N,J=J,aU=aU,W=W):
        aE=g^X
        if not aE:
            return
        p=1
        ab=0
        ar=aU
        Q=0
        while ar>1:
            if not(c[p]&aE):
                return
            aj=ar>>1
            h=o[p]
            j=w[p]
            if h!=g or j:
                bb(p,aj,h,j)
            W[Q]=p
            Q+=1
            aH=ab+aj
            if aO<aH:
                p<<=1
            else:
                p=p<<1|1
                ab=aH
            ar=aj
        I=c[p]&aE
        if not I:
            return
        if not P[p]:
            V(p)
        M=C[p]&X
        C[p]=M
        q[p]=(T[M&N]|S[M>>15])&G
        c[p]=M
        a[p]=M
        o[p]=g
        w[p]=0
        while Q:
            Q-=1
            p=W[Q]
            aa=p<<1
            U=aa|1
            if not P[p]:
                V(p)
            C[p]=C[aa]+C[U]
            q[p]=q[aa]+q[U]
            c[p]=c[aa]|c[U]
            a[p]=a[aa]&a[U]
    def co(aO,X,C=C,q=q,c=c,a=a,o=o,w=w,P=P,V=V,bb=bb,T=T,S=S,G=G,N=N,J=J,aU=aU,W=W):
        if not X:
            return
        p=1
        ab=0
        ar=aU
        Q=0
        while ar>1:
            if not(X&(g^a[p])):
                return
            aj=ar>>1
            h=o[p]
            j=w[p]
            if h!=g or j:
                bb(p,aj,h,j)
            W[Q]=p
            Q+=1
            aH=ab+aj
            if aO<aH:
                p<<=1
            else:
                p=p<<1|1
                ab=aH
            ar=aj
        I=X&(g^a[p])
        if not I:
            return
        if not P[p]:
            V(p)
        M=C[p]|X
        C[p]=M
        q[p]=(T[M&N]|S[M>>15])&G
        c[p]=M
        a[p]=M
        o[p]=g
        w[p]=0
        while Q:
            Q-=1
            p=W[Q]
            aa=p<<1
            U=aa|1
            if not P[p]:
                V(p)
            C[p]=C[aa]+C[U]
            q[p]=q[aa]+q[U]
            c[p]=c[aa]|c[U]
            a[p]=a[aa]&a[U]
    def a7(aO,M,C=C,q=q,c=c,a=a,o=o,w=w,P=P,V=V,bb=bb,T=T,S=S,G=G,N=N,bp=bp):
        p=1
        bc=bp-1
        while bc>=0:
            h=o[p]
            j=w[p]
            if h!=g or j:
                bb(p,1<<bc,h,j)
            p=(p<<1)|((aO>>bc)&1)
            bc-=1
        if C[p]==M:
            return
        if not P[p]:
            V(p)
        C[p]=M
        q[p]=(T[M&N]|S[M>>15])&G
        c[p]=M
        a[p]=M
        o[p]=g
        w[p]=0
        p>>=1
        while p:
            aa=p<<1
            U=aa|1
            if not P[p]:
                V(p)
            C[p]=C[aa]+C[U]
            q[p]=q[aa]+q[U]
            c[p]=c[aa]|c[U]
            a[p]=a[aa]&a[U]
            p>>=1
    def ci(aO,X,C=C,q=q,c=c,a=a,o=o,w=w,P=P,V=V,bb=bb,T=T,S=S,G=G,N=N,bp=bp):
        p=1
        bc=bp-1
        while bc>=0:
            h=o[p]
            j=w[p]
            if h!=g or j:
                bb(p,1<<bc,h,j)
            p=(p<<1)|((aO>>bc)&1)
            bc-=1
        ai=C[p]
        M=ai&X
        if M!=ai:
            if not P[p]:
                V(p)
            C[p]=M
            q[p]=(T[M&N]|S[M>>15])&G
            c[p]=M
            a[p]=M
            o[p]=g
            w[p]=0
            p>>=1
            while p:
                aa=p<<1
                U=aa|1
                if not P[p]:
                    V(p)
                C[p]=C[aa]+C[U]
                q[p]=q[aa]+q[U]
                c[p]=c[aa]|c[U]
                a[p]=a[aa]&a[U]
                p>>=1
        return M
    def cj(aO,X,C=C,q=q,c=c,a=a,o=o,w=w,P=P,V=V,bb=bb,T=T,S=S,G=G,N=N,bp=bp):
        p=1
        bc=bp-1
        while bc>=0:
            h=o[p]
            j=w[p]
            if h!=g or j:
                bb(p,1<<bc,h,j)
            p=(p<<1)|((aO>>bc)&1)
            bc-=1
        ai=C[p]
        M=ai|X
        if M!=ai:
            if not P[p]:
                V(p)
            C[p]=M
            q[p]=(T[M&N]|S[M>>15])&G
            c[p]=M
            a[p]=M
            o[p]=g
            w[p]=0
            p>>=1
            while p:
                aa=p<<1
                U=aa|1
                if not P[p]:
                    V(p)
                C[p]=C[aa]+C[U]
                q[p]=q[aa]+q[U]
                c[p]=c[aa]|c[U]
                a[p]=a[aa]&a[U]
                p>>=1
        return M
    def aN(aO,C=C,o=o,w=w,aU=aU):
        p=1
        ab=0
        ar=aU
        aw=g
        au=0
        while ar>1:
            aM=o[p]
            aR=w[p]
            if aw==g and au==0:
                aw=aM
                au=aR
            elif aM!=g or aR:
                bC=aw
                aw=(aM&bC)|au
                au=(aR&bC)|au
            aj=ar>>1
            aH=ab+aj
            if aO<aH:
                p<<=1
            else:
                p=p<<1|1
                ab=aH
            ar=aj
        return(C[p]&aw)|au
    def bj(aB,ax,C=C,q=q,c=c,a=a,o=o,w=w,T=T,S=S,N=N,J=J,aU=aU):
        ao=0
        p=1
        ab=0
        ar=aU
        aw=g
        au=0
        while True:
            if aB<=ab and ab+ar<=ax:
                if aw==g and au==0:
                    ao+=C[p]
                elif aw==au:
                    ao+=ar*au
                else:
                    aD=c[p]&(g^aw)
                    ap=au&(g^a[p])
                    I=aD|ap
                    if I:
                        B=T[I&N]|S[I>>15]
                        ao+=C[p]+ar*ap-((q[p]&B)%J)
                    else:
                        ao+=C[p]
                return ao
            aM=o[p]
            aR=w[p]
            if aw==g and au==0:
                bi=aM
                bq=aR
            elif aM==g and aR==0:
                bi=aw
                bq=au
            else:
                bi=(aM&aw)|au
                bq=(aR&aw)|au
            aj=ar>>1
            aH=ab+aj
            if ax<=aH:
                p<<=1
                ar=aj
                aw=bi
                au=bq
                continue
            if aB>=aH:
                p=p<<1|1
                ab=aH
                ar=aj
                aw=bi
                au=bq
                continue
            D=p<<1
            ad=ab
            L=aj
            ak=bi
            an=bq
            while True:
                if aB<=ad:
                    if ak==g and an==0:
                        ao+=C[D]
                    elif ak==an:
                        ao+=L*an
                    else:
                        aD=c[D]&(g^ak)
                        ap=an&(g^a[D])
                        I=aD|ap
                        if I:
                            B=T[I&N]|S[I>>15]
                            ao+=C[D]+L*ap-((q[D]&B)%J)
                        else:
                            ao+=C[D]
                    break
                aM=o[D]
                aR=w[D]
                if ak==g and an==0:
                    aL=aM
                    aP=aR
                elif aM==g and aR==0:
                    aL=ak
                    aP=an
                else:
                    aL=(aM&ak)|an
                    aP=(aR&ak)|an
                x=L>>1
                ah=ad+x
                if aB>=ah:
                    D=D<<1|1
                    ad=ah
                    L=x
                    ak=aL
                    an=aP
                else:
                    R=D<<1|1
                    if aL==g and aP==0:
                        ao+=C[R]
                    elif aL==aP:
                        ao+=x*aP
                    else:
                        aD=c[R]&(g^aL)
                        ap=aP&(g^a[R])
                        I=aD|ap
                        if I:
                            B=T[I&N]|S[I>>15]
                            ao+=C[R]+x*ap-((q[R]&B)%J)
                        else:
                            ao+=C[R]
                    D<<=1
                    L=x
                    ak=aL
                    an=aP
            D=p<<1|1
            ad=aH
            L=aj
            ak=bi
            an=bq
            while True:
                if ad+L<=ax:
                    if ak==g and an==0:
                        ao+=C[D]
                    elif ak==an:
                        ao+=L*an
                    else:
                        aD=c[D]&(g^ak)
                        ap=an&(g^a[D])
                        I=aD|ap
                        if I:
                            B=T[I&N]|S[I>>15]
                            ao+=C[D]+L*ap-((q[D]&B)%J)
                        else:
                            ao+=C[D]
                    break
                aM=o[D]
                aR=w[D]
                if ak==g and an==0:
                    aL=aM
                    aP=aR
                elif aM==g and aR==0:
                    aL=ak
                    aP=an
                else:
                    aL=(aM&ak)|an
                    aP=(aR&ak)|an
                x=L>>1
                ah=ad+x
                if ax<=ah:
                    D<<=1
                    L=x
                    ak=aL
                    an=aP
                else:
                    R=D<<1
                    if aL==g and aP==0:
                        ao+=C[R]
                    elif aL==aP:
                        ao+=x*aP
                    else:
                        aD=c[R]&(g^aL)
                        ap=aP&(g^a[R])
                        I=aD|ap
                        if I:
                            B=T[I&N]|S[I>>15]
                            ao+=C[R]+x*ap-((q[R]&B)%J)
                        else:
                            ao+=C[R]
                    D=D<<1|1
                    ad=ah
                    L=x
                    ak=aL
                    an=aP
            return ao
    def bY():
        bA.clear()
    def br(C=C,q=q,c=c,a=a,o=o,w=w,P=P,bt=bt,bn=bn,bH=bH,bG=bG,bA=bA):
        for p in bA:
            C[p]=bt[p]
            q[p]=bn[p]
            c[p]=bH[p]
            a[p]=bG[p]
            o[p]=g
            w[p]=0
            P[p]=0
        bA.clear()
    return(aU,bY,br,a7,aN,a_,a8,bj)
def ca(bR):
    (n,m,aX,bT,bO,a6,bv,bo,aC,bx,a5)=bR
    aV=[]
    a2=aV.append
    bD=sys.stdout.write
    if n==1:
        bu=aX[0]
        ae=0
        while ae<aC:
            aQ=bu
            y=ae+1
            aA=a5[ae]
            z=((bx[ae]+1)%m)+1
            while aA:
                O=a6[z]^y
                if z&1:
                    aQ&=O
                else:
                    aQ|=O
                y=aQ
                z+=1
                if z>m:
                    z=1
                aA-=1
            a2(str(y))
            ae+=1
        bD("\n".join(aV)+("\n"if aV else""))
        return
    bQ=n-1
    bz=aX[-1]
    (aU,bY,br,a7,aN,a_,a8,bj)=b_(aX[:-1])
    bL=1<<n.bit_length()
    aY={}
    b6=16
    ae=0
    while ae<aC:
        bY()
        az=bz
        y=ae+1
        aA=a5[ae]
        z=((bx[ae]+1)%m)+1
        by=False
        at=-1
        bd=0
        aF=0
        while aA:
            if y>=bL:
                O=a6[z]^y
                if z&1:
                    az&=O
                else:
                    az|=O
                y=az
                z+=1
                if z>m:
                    z=1
                aA-=1
                continue
            u=bT[z]^y
            if u<1:
                u=1
            elif u>n:
                u=n
            v=bO[z]^y
            if v<1:
                v=1
            elif v>n:
                v=n
            if u<=v:
                be=u-1
                aW=v
            else:
                be=v-1
                aW=u
            u=bv[z]^y
            if u<1:
                u=1
            elif u>n:
                u=n
            v=bo[z]^y
            if v<1:
                v=1
            elif v>n:
                v=n
            if u<=v:
                a9=u-1
                a0=v
            else:
                a9=v-1
                a0=u
            O=a6[z]^y
            a3=z&1
            if aW==n:
                if a3:
                    az&=O
                else:
                    az|=O
                al=bQ
            else:
                al=aW
            av=be
            if av<al:
                if al-av==1:
                    aO=av
                    if not by:
                        if aO==at:
                            ai=aF
                        elif at<0:
                            ay=aN(aO)
                            at=aO
                            bd=ay
                            aF=ay
                            ai=ay
                        else:
                            aY[at]=[bd,aF]
                            by=True
                            ay=aN(aO)
                            bg=[ay,ay]
                            aY[aO]=bg
                            ai=ay
                        if a3:
                            M=ai&O
                        else:
                            M=ai|O
                        if M!=ai:
                            if by:
                                bg[1]=M
                            else:
                                aF=M
                    else:
                        bg=aY.get(aO)
                        if bg is None:
                            if len(aY)>=b6:
                                for bF,bK in aY.items():
                                    a7(bF,bK[1])
                                aY.clear()
                                by=False
                                at=aO
                                ay=aN(aO)
                                bd=ay
                                aF=ay
                                ai=ay
                                if a3:
                                    M=ai&O
                                else:
                                    M=ai|O
                                if M!=ai:
                                    aF=M
                            else:
                                ay=aN(aO)
                                bg=[ay,ay]
                                aY[aO]=bg
                                ai=ay
                                if a3:
                                    M=ai&O
                                else:
                                    M=ai|O
                                if M!=ai:
                                    bg[1]=M
                        else:
                            ai=bg[1]
                            if a3:
                                M=ai&O
                            else:
                                M=ai|O
                            if M!=ai:
                                bg[1]=M
                else:
                    if a3:
                        a_(av,al,O)
                        if by:
                            for aO,bg in aY.items():
                                if av<=aO<al:
                                    bg[0]&=O
                                    bg[1]&=O
                        elif at>=av and at<al:
                            bd&=O
                            aF&=O
                    else:
                        a8(av,al,O)
                        if by:
                            for aO,bg in aY.items():
                                if av<=aO<al:
                                    bg[0]|=O
                                    bg[1]|=O
                        elif at>=av and at<al:
                            bd|=O
                            aF|=O
            if a0==n:
                ao=az
                aJ=bQ
            else:
                ao=0
                aJ=a0
            aT=a9
            if aT<aJ:
                if aJ-aT==1:
                    if by:
                        bg=aY.get(aT)
                        if bg is None:
                            ao+=aN(aT)
                        else:
                            ao+=bg[1]
                    elif aT==at:
                        ao+=aF
                    else:
                        ao+=aN(aT)
                else:
                    if by:
                        for bF,bK in aY.items():
                            a7(bF,bK[1])
                        aY.clear()
                        by=False
                        at=-1
                    elif at>=0:
                        a7(at,aF)
                        at=-1
                    ao+=bj(aT,aJ)
            y=ao&g
            z+=1
            if z>m:
                z=1
            aA-=1
        if by:
            aY.clear()
        a2(str(y))
        br()
        if len(aV)==4096:
            bD("\n".join(aV)+"\n")
            aV.clear()
        ae+=1
    if aV:
        bD("\n".join(aV)+"\n")
def bW(bR,ce=3):
    (n,m,aX,bT,bO,a6,bv,bo,aC,bx,a5)=bR
    aV=[];a2=aV.append;bD=sys.stdout.write
    if n==1:
        bu=aX[0]
        for ae in range(aC):
            aQ=bu;y=ae+1
            aA=a5[ae]
            z=((bx[ae]+1)%m)+1
            while aA:
                X=a6[z]^y
                aQ=aQ&X if z&1 else aQ|X
                y=aQ;z=z+1 if z<m else 1;aA-=1
            a2(str(y))
        bD("\n".join(aV)+("\n"if aV else""));return
    bQ=n-1;bz=aX[-1];vm=g
    bm=0
    for aQ in aX[:-1]:bm|=aQ
    bI=[0]*30
    bE=bm
    while bE:
        bJ=bE&-bE;b=bJ.bit_length()-1
        cp=bytearray((bQ+7)>>3)
        for i,aQ in enumerate(aX[:-1]):
            if aQ&bJ:cp[i>>3]|=1<<(i&7)
        bI[b]=int.from_bytes(cp,"little")
        bE-=bJ
    a1=None
    bM=n.bit_length();bX=bM;bN=bM<<1
    b1=bN+30;b0=(1<<bM)-1
    bL=1<<n.bit_length()
    for ae in range(aC):
        b3=bI.copy();a4=bm
        az=bz;y=ae+1
        aA=a5[ae]
        z=((bx[ae]+1)%m)+1
        ba=True;b4=[];b7=b4 .append
        if a1 is not None:
            aU,bY,br,a7,aN,a_,a8,bj=a1
        while aA:
            if y>=bL:
                O=a6[z]^y
                az=az&O if z&1 else az|O
                y=az;z=z+1 if z<m else 1;aA-=1;continue
            u=bT[z]^y
            u=1 if u<1 else n if u>n else u
            v=bO[z]^y
            v=1 if v<1 else n if v>n else v
            if u<=v:be=u-1;aW=v
            else:be=v-1;aW=u
            u=bv[z]^y
            u=1 if u<1 else n if u>n else u
            v=bo[z]^y
            v=1 if v<1 else n if v>n else v
            if u<=v:a9=u-1;a0=v
            else:a9=v-1;a0=u
            O=a6[z]^y;a3=z&1
            if aW==n:
                az=az&O if a3 else az|O
                al=bQ
            else:al=aW
            av=be
            if ba and av<al:
                if not a3:
                    ch=(O&vm)&~a4
                    if a4 .bit_count()+ch.bit_count()>ce:
                        if a1 is None:
                            a1=b_(aX[:-1])
                        aU,bY,br,a7,aN,a_,a8,bj=a1
                        bY()
                        for cf in b4:
                            rl=cf&b0;rr=(cf>>bX)&b0
                            rm=(cf>>bN)&vm
                            if cf>>b1:a_(rl,rr,rm)
                            else:a8(rl,rr,rm)
                        b4 .clear();ba=False
                if ba:
                    ar=al-av
                    b8=((1<<ar)-1)<<av
                    if a3:
                        bw=a4&(vm^O)
                        while bw:
                            bJ=bw&-bw;b=bJ.bit_length()-1
                            aQ=b3[b]&~b8;b3[b]=aQ
                            if aQ==0:a4^=bJ
                            bw-=bJ
                    else:
                        bw=O&vm
                        while bw:
                            bJ=bw&-bw;b=bJ.bit_length()-1
                            b3[b]|=b8;a4|=bJ;bw-=bJ
                    b7(av|(al<<bX)|((O&vm)<<bN)|(a3<<b1))
                else:
                    if a3:a_(av,al,O)
                    else:a8(av,al,O)
            elif not ba and av<al:
                if a3:a_(av,al,O)
                else:a8(av,al,O)
            ao=az if a0==n else 0
            aJ=bQ if a0==n else a0
            if a9<aJ:
                if ba:
                    bZ=aJ-a9
                    ck=(1<<bZ)-1
                    bw=a4
                    while bw:
                        bJ=bw&-bw;b=bJ.bit_length()-1
                        ao+=(((b3[b]>>a9)&ck).bit_count())<<b
                        bw-=bJ
                else:
                    ao+=bj(a9,aJ)
            y=ao&vm
            z=z+1 if z<m else 1;aA-=1
        a2(str(y))
        if not ba:br()
        if len(aV)==4096:
            bD("\n".join(aV)+"\n");aV.clear()
    if aV:bD("\n".join(aV)+"\n")
def cr():
    bR=b9()
    aX=bR[2]
    bE=0
    for aQ in aX[:-1]:bE|=aQ
    if bE.bit_count()<=5:
        bW(bR,5)
    else:
        ca(bR)
if __name__=="__main__":
    cr()