結果
| 問題 | No.3671 Reusable Lazy Segment Tree |
| コンテスト | |
| ユーザー |
 harurun
|
| 提出日時 | 2026-08-05 16:35:37 |
| 言語 | PyPy3 (7.3.23 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 60,131 bytes |
| 記録 | |
| コンパイル時間 | 254 ms |
| コンパイル使用メモリ | 96,592 KB |
| 実行使用メモリ | 256,040 KB |
| 最終ジャッジ日時 | 2026-09-04 22:04:35 |
| 合計ジャッジ時間 | 13,108 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 TLE * 1 -- * 8 |
ソースコード
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()