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 #import pypyjit #pypyjit.set_param('max_unroll_recursion=-1') #sys.set_int_max_str_digits(10**9) 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