import sys sys.setrecursionlimit(400000) class SegTree: def __init__(self,op,e,v): self._op=op self._e=e if isinstance(v,int): v=[e]*v self._n=len(v) self._log=self.ceil2() self._size=1<>i) return def get(self,p): return self._d[p+self._size] def prod(self,left,right): sml=self._e smr=self._e left+=self._size right+=self._size while left>=1 right>>=1 return self._op(sml,smr) def all_prod(self): return self._d[1] def max_right(self,left,target): self.target=target if left==self._n: return self._n left+=self._size sm=self._e first=True while first or (left & -left)!=left: first=False while left%2==0: left>>=1 if not self._f(self._op(sm,self._d[left])): while left1 and right%2: right>>=1 if not self._f(self._op(self._d[right],sm)): while right