import collections,sys,math,functools,operator,itertools,bisect,heapq,decimal,string,time,random #sys.setrecursionlimit(10**9) #https://github.com/shakayami/ACL-for-python/blob/master/lazysegtree.py class lazy_segtree(): def update(self,k):self.d[k]=self.op(self.d[2*k],self.d[2*k+1]) def all_apply(self,k,f): self.d[k]=self.mapping(f,self.d[k]) if (k>i) self.d[p]=x for i in range(1,self.log+1):self.update(p>>i) def get(self,p): assert 0<=p and p>i) return self.d[p] def prod(self,l,r): assert 0<=l and l<=r and r<=self.n if l==r:return self.e l+=self.size r+=self.size for i in range(self.log,0,-1): if (((l>>i)<>i) if (((r>>i)<>i) sml,smr=self.e,self.e while(l>=1 r>>=1 return self.op(sml,smr) def all_prod(self):return self.d[1] def apply_point(self,p,f): assert 0<=p and p>i) self.d[p]=self.mapping(f,self.d[p]) for i in range(1,self.log+1):self.update(p>>i) def apply(self,l,r,f): assert 0<=l and l<=r and r<=self.n if l==r:return l+=self.size r+=self.size for i in range(self.log,0,-1): if (((l>>i)<>i) if (((r>>i)<>i) l2,r2=l,r while(l>=1 r>>=1 l,r=l2,r2 for i in range(1,self.log+1): if (((l>>i)<>i) if (((r>>i)<>i) def max_right(self,l,g): assert 0<=l and l<=self.n assert g(self.e) if l==self.n:return self.n l+=self.size for i in range(self.log,0,-1):self.push(l>>i) sm=self.e while(1): while(l%2==0):l>>=1 if not(g(self.op(sm,self.d[l]))): while(l>i) sm=self.e while(1): r-=1 while(r>1 and (r%2)):r>>=1 if not(g(self.op(self.d[r],sm))): while(r