import bisect import copy import decimal import fractions import heapq import itertools import math import random import sys import time from collections import Counter,deque,defaultdict from functools import lru_cache,reduce from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max def _heappush_max(heap,item): heap.append(item) heapq._siftdown_max(heap, 0, len(heap)-1) def _heappushpop_max(heap, item): if heap and item < heap[0]: item, heap[0] = heap[0], item heapq._siftup_max(heap, 0) return item from math import gcd as GCD read=sys.stdin.read readline=sys.stdin.readline readlines=sys.stdin.readlines write=sys.stdout.write class Segment_Tree: def __init__(self,N,f,e,lst=None,dynamic=False): self.f=f self.e=e self.N=N if dynamic: self.segment_tree=defaultdict(lambda:self.e) else: if lst==None: self.segment_tree=[self.e]*2*self.N else: assert len(lst)<=self.N self.segment_tree=[self.e]*self.N+[x for x in lst]+[self.e]*(N-len(lst)) for i in range(self.N-1,0,-1): self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def __getitem__(self,i): if type(i)==int: if -self.N<=i<0: return self.segment_tree[i+self.N*2] elif 0<=i1: i>>= 1 self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def Build(self,lst): for i,x in enumerate(lst,self.N): self.segment_tree[i]=x for i in range(self.N-1,0,-1): self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def Fold(self,L=None,R=None): if L==None: L=self.N else: L+=self.N if R==None: R=self.N*2 else: R+=self.N vL=self.e vR=self.e while L>=1 R>>=1 return self.f(vL,vR) def Fold_Index(self,L=None,R=None): if L==None: L=self.N else: L+=self.N if R==None: R=self.N*2 else: R+=self.N if L==R: return None x=self.Fold(L-self.N,R-self.N) while L>=1 R>>=1 while i>=1 r>>=1 if f(self.f(vl,vr)): return self.N v=self.e while True: while L%2==0: L>>=1 vv=self.f(v,self.segment_tree[L]) if f(vv): v=vv L+=1 else: while L>=1 r>>=1 if f(self.f(vl,vr)): return 0 v=self.e while True: R-=1 while R>1 and R%2: R>>=1 vv=self.f(self.segment_tree[R],v) if f(vv): v=vv else: while R1: i>>=1 idxN.append(i) while j>1: j>>=1 idxM.append(j) i=idxN[0] for j in idxM[1:]: self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1]) for i in idxN[1:]: for j in idxM: self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j]) def Build(self,lst): assert len(lst)<=self.N assert all(len(lst[i] for i in range(self.N))<=self.M) for i in range(len(lst)): for j in range(len(lst[i])): self.segment_tree[i+self.N][j+self.M]=lst[i][j] for i in range(self.N-1,0,-1): for j in range(2*self.M-1,self.M-1,-1): self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j]) for i in range(2*self.N-1,-1,-1): for j in range(self.M-1,0,-1): self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1]) def Fold(self,LN=None,RN=None,LM=None,RM=None): LN+=self.N RN+=self.N LM+=self.M RM+=self.M idxN=[] idxM=[] while LN>=1 RN>>=1 while LM>=1 RM>>=1 retu=self.e for i in idxN: for j in idxM: retu=self.f(retu,self.segment_tree[i][j]) return retu def Fold_Index(self,LN=None,RN=None,LM=None,RM=None): if LN==None: LN=self.N else: LN+=self.N if RN==None: RN=self.N*2 else: RN+=self.N if LM==None: LM=self.M else: LM+=self.M if RM==None: RM=self.M*2 else: RM+=self.M if LN==RN and LM==RM: return None idxN=[] idxM=[] while LN>=1 RN>>=1 while LM>=1 RM>>=1 v=self.e for i in idxN: for j in idxM: v=self.f(v,self.segment_tree[i][j]) for i in idxN: for j in idxM: if v==self.f(v,self.segment_tree[i][j]): break else: continue break while i>h) def Operate_Range(self,a,L=None,R=None): if L==None: L=self.N else: L+=self.N if R==None: R=self.N*2 else: R+=self.N L0=L//(L&-L) R0=R//(R&-R)-1 self.Propagate_Above(L0) self.Propagate_Above(R0) while L>=1 R>>=1 def Update(self): for i in range(1,self.N): self.Propagate_At(i) self.segment_tree_act[i]=self.e_act def __str__(self): import copy segment_tree_act=copy.deepcopy(self.segment_tree_act) for i in range(1,self.N): segment_tree_act[i<<1]=self.f_act(segment_tree_act[i<<1],segment_tree_act[i]) segment_tree_act[i<<1|1]=self.f_act(segment_tree_act[i<<1|1],segment_tree_act[i]) segment_tree_act[i]=self.e_act segment_tree_act[i]=self.e_act return "["+", ".join(map(str,[self.operate(x,a) for x,a in zip(self.lst,segment_tree_act[self.N:])]))+"]" class Lazy_Segment_Tree: def __init__(self,N,f,e,f_act,e_act,operate,lst=None): self.N=N self.f=f self.e=e self.f_act=f_act self.e_act=e_act self.operate=operate self.segment_tree=[self.e]*(self.N+self.N) self.segment_tree_act=[self.e_act]*(self.N+self.N) if lst!=None: for i,x in enumerate(lst): self.segment_tree[i+self.N]=x for i in range(self.N-1,0,-1): self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) self.segment_tree_act=[self.e_act]*(self.N+self.N) def __getitem__(self,i): if type(i) is int: if -self.N<=i<0: i+=self.N*2 elif 0<=i>h) def Recalculate_Above(self,i): while i>1: i>>=1 self.segment_tree[i]=self.f(self.Operate_At(i<<1),self.Operate_At(i<<1|1)) def Build(self,lst): for i,x in enumerate(lst): self.segment_tree[i+self.N]=x for i in range(self.N-1,0,-1): self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) self.segment_tree_act=[self.e_act]*(self.N+self.N) def Fold(self,L=None,R=None): if L==None: L=self.N else: L+=self.N if R==None: R=self.N*2 else: R+=self.N self.Propagate_Above(L//(L&-L)) self.Propagate_Above(R//(R&-R)-1) vL=self.e vR=self.e while L>=1 R>>=1 return self.f(vL,vR) def Fold_Index(self,L=None,R=None): if L==None: L=self.N else: L+=self.N if R==None: R=self.N*2 else: R+=self.N if L==R: return None x=self.Fold(L-self.N,R-self.N) while L>=1 R>>=1 while i>=1 R>>=1 self.Recalculate_Above(L0) self.Recalculate_Above(R0) def Update(self): for i in range(1,self.N): self.Propagate_At(i) for i in range(self.N,self.N*2): self.segment_tree[i]=self.Operate_At(i) self.segment_tree_act[i]=self.e_act for i in range(self.N-1,0,-1): self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1]) def Bisect_Right(self,L=None,f=None): if L==self.N: return self.N if L==None: L=0 L+=self.N self.Propagate_Above(L//(L&-L)) self.Propagate_Above(self.N//(self.N&-self.N)-1) l,r=L,self.N*2 vl=self.e vr=self.e while l>=1 r>>=1 if f(self.f(vl,vr)): return self.N v=self.e self.Propagate_Above(L) while True: while L%2==0: L>>=1 vv=self.f(v,self.Operate_At(L)) if f(vv): v=vv L+=1 else: while L>=1 r>>=1 if f(self.f(vl,vr)): return 0 v=self.e self.Propagate_Above(R-1) while True: R-=1 while R>1 and R%2: R>>=1 vv=self.f(self.Operate_At(R),v) if f(vv): v=vv else: while R