import math import collections import heapq import bisect import sys import copy import itertools from collections import defaultdict import random sys.setrecursionlimit(6*10**5) from sortedcontainers import SortedSet, SortedList, SortedDict import hashlib def new_hasher(): return hashlib.blake2b(digest_size=16) ''' h = new_hasher() h.update(s.encode()) S = h.digest() ''' def I():return input() def II():return int(input()) def IS():return input().split() def MI():return map(int,input().split()) def LS():return list(input().split()) def LI():return list(map(int,input().split())) def LC():return list(input()) #0index def MI0():return map(lambda x:int(x)-1,input().split()) def LI0():return list(map(lambda x:int(x)-1,input().split())) mod=998244353 MOD=10**9+7 #階乗 def Factorial(n,mod): c=1 for i in range(2,n+1): c*=i c%=mod return c #階乗リスト def FactorialList(n,mod): c=[1,1] for i in range(2,n+1): c.append(c[-1]*i%mod) return c #コンビネーション #階乗が前計算してある時はそれを使う def CMB(n,k): if n==k or k==0: return 1 c=1 for i in range(k+1,n+1): c*=i c%=mod d=1 for i in range(2,n-k+1): d*=i d%=mod return c*pow(d,-1,mod)%mod #最小公倍数 def LCM(a,b): return math.gcd(a*b//math.gcd(a,b)) #素数列挙 def eratosthenes(n): isPrimes = [True] * (n+1) isPrimes[0], isPrimes[1] = False, False for i in range(2, int(n**0.5)+1): if isPrimes[i]: for j in range(2*i, n+1, i): isPrimes[j] = False return [i for i in range(2, n+1) if isPrimes[i]] #二つの線分の交差判定(a=[2,-1],b=[-3,-3]などで与える） def max_min_cross(p1, p2, p3, p4): min_ab, max_ab = min(p1, p2), max(p1, p2) min_cd, max_cd = min(p3, p4), max(p3, p4) if min_ab > max_cd or max_ab < min_cd: return False return True def cross_judge(a, b, c, d): # x座標による判定 if not max_min_cross(a[0], b[0], c[0], d[0]): return False # y座標による判定 if not max_min_cross(a[1], b[1], c[1], d[1]): return False tc1 = (a[0] - b[0]) * (c[1] - a[1]) + (a[1] - b[1]) * (a[0] - c[0]) tc2 = (a[0] - b[0]) * (d[1] - a[1]) + (a[1] - b[1]) * (a[0] - d[0]) td1 = (c[0] - d[0]) * (a[1] - c[1]) + (c[1] - d[1]) * (c[0] - a[0]) td2 = (c[0] - d[0]) * (b[1] - c[1]) + (c[1] - d[1]) * (c[0] - b[0]) return tc1 * tc2 <= 0 and td1 * td2 <= 0 #dfs(start-goal経路) import sys sys.setrecursionlimit(6*10**5) def dfs(start, goal, adj_list): visited = [False] * len(adj_list) path = [] def dfs_util(node): if node == goal: path.append(node) return True visited[node] = True path.append(node) for neighbor in adj_list[node]: if not visited[neighbor]: if dfs_util(neighbor): return True path.pop() return False if dfs_util(start): return path else: return None #根付き木の深さ、辺の長さ1のrootからの距離 def bfs(graph,root): a=[-1 for i in range(len(graph))] now={root*75} a[root]=0 c=1 while now: new=set() for i in now: for j in graph[i//75]: if a[j]==-1: new.add(j*75) a[j]=c now=new c+=1 return a #ダイクストラ法 import heapq def dijkstra(graph, start=0): num_node = len(graph) inf = float('inf') distances = [inf] * num_node distances[start] = 0 pq = [(0, start)] while pq: current_distance, current_node = heapq.heappop(pq) if current_distance > distances[current_node]: continue for neighbor, weight in graph[current_node]: distance = current_distance + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(pq, (distance, neighbor)) return distances #BIT class BIT: def __init__(self, n): self.size=n self.tree = [0] * (n+1) def add(self, i,x): while i <= self.size: self.tree[i] += x i += i & -i def sum(self, i): total = 0 while i >0: total += self.tree[i] i -= i & -i return total #転倒数(BITも貼る) def InversionNumberByBIT(A): ans = 0 Bit = BIT(len(A)) for i in range(len(A)): ans += i - Bit.sum(A[i]) Bit.add(A[i], 1) return ans #座圧 def zaatsu(before_list): set_sort = sorted(list(set(before_list))) rank = {x:i+1 for i,x in enumerate(set_sort)} after_list = [] for tmp in before_list: after_list.append(rank[tmp]) return after_list #座圧して転倒数を計算 def InversionNumberByBIT2(A): return InversionNumberByBIT(zaatsu(A)) #約数列挙 def divisor(n): sq = n**0.5 border = int(sq) table = [] bigs = [] for small in range(1, border+1): if n%small == 0: table.append(small) big = n//small bigs.append(big) if border == sq: bigs.pop() table += reversed(bigs) return table #遅延pq、削除命令がO(1) import heapq class LazyHeap: def __init__(self, A): self.heap = A[:] heapq.heapify(self.heap) self.deleted = {} def push(self, x): heapq.heappush(self.heap, x) def erase(self, x): self.deleted[x] = self.deleted.get(x, 0) + 1 def _clean(self): while self.heap: x = self.heap[0] if x not in self.deleted: break if self.deleted[x] == 1: del self.deleted[x] else: self.deleted[x] -= 1 heapq.heappop(self.heap) def top(self): self._clean() return self.heap[0] def pop(self): self._clean() return heapq.heappop(self.heap) def empty(self): self._clean() return len(self.heap) == 0 #素因数分解 def prime_factorize(n): a = [] while n % 2 == 0: a.append(2) n //= 2 f = 3 while f * f <= n: if n % f == 0: a.append(f) n //= f else: f += 2 if n != 1: a.append(n) return a #素因数分解した結果を辞書形式で返す import collections def prime_factorize2(n): return collections.Counter(prime_factorize(n)) #最大増加部分列(長さのみ) def LIS(a, inf = 1e18) : n = len(a) dp = [inf] * n for i in range(n) : pos = bisect.bisect_left(dp, a[i]) dp[pos] = a[i] return bisect.bisect_left(dp, inf) #行列累乗 def mat_mul(A, B, mod): n = len(A) m = len(B[0]) p = len(B) C = [[0] * m for _ in range(n)] for i in range(n): for k in range(p): if A[i][k] == 0: continue a = A[i][k] for j in range(m): C[i][j] = (C[i][j] + a * B[k][j]) % mod return C def mat_pow(A, e, mod): n = len(A) R = [[0] * n for _ in range(n)] for i in range(n): R[i][i] = 1 while e: if e & 1: R = mat_mul(R, A, mod) A = mat_mul(A, A, mod) e >>= 1 return R #Aが一次元の行列の場合 #A_n=M^(n-1)A_1 をもとめる。 def A_n(A_1,M,n,mod): S=[[A_1[i]] for i in range(len(A_1))] return mat_mul(S,mat_pow(M,n-1,mod),mod) #UnionFind from collections import defaultdict class UnionFind: def __init__(self, n): self.n = n self.parents = [-1] * n def find(self, x): if self.parents[x] < 0: return x else: self.parents[x] = self.find(self.parents[x]) return self.parents[x] def union(self, x, y): x = self.find(x) y = self.find(y) if x == y: return if self.parents[x] > self.parents[y]: x, y = y, x self.parents[x] += self.parents[y] self.parents[y] = x def size(self, x): return -self.parents[self.find(x)] def same(self, x, y): return self.find(x) == self.find(y) #注O(n) def members(self, x): root = self.find(x) return [i for i in range(self.n) if self.find(i) == root] def roots(self): return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): return len(self.roots()) def all_group_members(self): group_members = defaultdict(list) for member in range(self.n): group_members[self.find(member)].append(member) return group_members def __str__(self): return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items()) #クラスカル法（UFも貼ること） def kruskal(adj_list): edges = [] n = len(adj_list) for u in range(n): for v, weight in adj_list[u]: if u < v: edges.append((weight, u, v)) edges.sort() uf = UnionFind(n) mst_weight = 0 mst_edges = [] for weight, u, v in edges: if uf.find(u) != uf.find(v): uf.union(u, v) mst_weight += weight mst_edges.append((u, v)) return mst_weight, mst_edges #重み付きUF class WeightedUnionFind: def __init__(self, n): self.par = [i for i in range(n+1)] self.rank = [0] * (n+1) # 根への距離を管理 self.weight = [0] * (n+1) # 検索 def find(self, x): if self.par[x] == x: return x else: y = self.find(self.par[x]) # 親への重みを追加しながら根まで走査 self.weight[x] += self.weight[self.par[x]] self.par[x] = y return y # 併合 def union(self, x, y, w): rx = self.find(x) ry = self.find(y) # xの木の高さ < yの木の高さ if self.rank[rx] < self.rank[ry]: self.par[rx] = ry self.weight[rx] = w - self.weight[x] + self.weight[y] # xの木の高さ ≧ yの木の高さ else: self.par[ry] = rx self.weight[ry] = -w - self.weight[y] + self.weight[x] # 木の高さが同じだった場合の処理 if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1 # 同じ集合に属するか def same(self, x, y): return self.find(x) == self.find(y) # xからyへのコスト def diff(self, x, y): return self.weight[x] - self.weight[y] #なもりグラフの循環している部分を列挙 def get_cycles(to): n = len(to) state = [0] * n # 0:未訪問, 1:探索中, 2:探索終了 cycles = [] for s in range(n): if state[s]: continue v = s pos = {} path = [] while state[v] == 0: state[v] = 1 pos[v] = len(path) path.append(v) v = to[v] if state[v] == 1 and v in pos: cycles.append(path[pos[v]:]) for x in path: state[x] = 2 return cycles #segfunc def segfunc(x,y):return x+y def segfunc(x,y):return x*y #セグ木 class SegTree: def __init__(self, init_val, segfunc, ide_ele): n = len(init_val) self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 while self.num < n: self.num <<= 1 self.tree = [ide_ele] * (2 * self.num) for i in range(n): self.tree[self.num + i] = init_val[i] for i in range(self.num - 1, 0, -1): self.tree[i] = self.segfunc( self.tree[i << 1], self.tree[i << 1 | 1] ) def add(self, k, x): k += self.num self.tree[k] += x while k > 1: k >>= 1 self.tree[k] = self.segfunc( self.tree[k << 1], self.tree[k << 1 | 1] ) def update(self, k, x): k += self.num self.tree[k] = x while k > 1: k >>= 1 self.tree[k] = self.segfunc( self.tree[k << 1], self.tree[k << 1 | 1] ) def query(self, l, r): res = self.ide_ele l += self.num r += self.num while l < r: if l & 1: res = self.segfunc(res, self.tree[l]) l += 1 if r & 1: r -= 1 res = self.segfunc(res, self.tree[r]) l >>= 1 r >>= 1 return res def bisect_left(self, x): l = 0 r = self.num while l < r: m = (l + r) >> 1 if self.tree[self.num + m] < x: l = m + 1 else: r = m return l def bisect_right(self, x): l = 0 r = self.num while l < r: m = (l + r) >> 1 if self.tree[self.num + m] <= x: l = m + 1 else: r = m return l #遅延セグ木（区間加算用） class LazySegTree_RAQ: def __init__(self, init_val, segfunc, ide_ele): n = len(init_val) self.n = n self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 while self.num < n: self.num <<= 1 self.tree = [ide_ele] * (2 * self.num) self.lazy = [0] * (2 * self.num) self.mx = [float("-inf")] * (2 * self.num) for i in range(n): self.tree[self.num + i] = init_val[i] self.mx[self.num + i] = init_val[i] for i in range(self.num - 1, 0, -1): self.tree[i] = self.segfunc( self.tree[2 * i], self.tree[2 * i + 1] ) self.mx[i] = max( self.mx[2 * i], self.mx[2 * i + 1] ) def gindex(self, l, r): l += self.num r += self.num # bit_length() を使わない lm = l while lm & -lm != lm: lm -= lm & -lm rm = r while rm & -rm != rm: rm -= rm & -rm lm = l >> 1 rm = r >> 1 while r > l: if l <= lm: yield l if r <= rm: yield r r >>= 1 l >>= 1 while l: yield l l >>= 1 def propagates(self, *ids): for i in reversed(ids): v = self.lazy[i] if v == 0: continue self.lazy[i] = 0 self.lazy[2 * i] += v self.lazy[2 * i + 1] += v self.tree[2 * i] += v self.tree[2 * i + 1] += v self.mx[2 * i] += v self.mx[2 * i + 1] += v def lazy_push(self, k): v = self.lazy[k] if v == 0: return self.lazy[k] = 0 self.lazy[2 * k] += v self.lazy[2 * k + 1] += v self.tree[2 * k] += v self.tree[2 * k + 1] += v self.mx[2 * k] += v self.mx[2 * k + 1] += v def add(self, l, r, x): ids = self.gindex(l, r) l += self.num r += self.num while l < r: if l & 1: self.lazy[l] += x self.tree[l] += x self.mx[l] += x l += 1 if r & 1: r -= 1 self.lazy[r] += x self.tree[r] += x self.mx[r] += x l >>= 1 r >>= 1 for i in ids: self.tree[i] = ( self.segfunc( self.tree[2 * i], self.tree[2 * i + 1] ) + self.lazy[i] ) self.mx[i] = ( max( self.mx[2 * i], self.mx[2 * i + 1] ) + self.lazy[i] ) def query(self, l, r): self.propagates(*self.gindex(l, r)) res = self.ide_ele l += self.num r += self.num while l < r: if l & 1: res = self.segfunc(res, self.tree[l]) l += 1 if r & 1: res = self.segfunc(res, self.tree[r - 1]) l >>= 1 r >>= 1 return res def bisect_left(self, x): if self.mx[1] < x: return self.n k = 1 while k < self.num: self.lazy_push(k) if self.mx[2 * k] >= x: k *= 2 else: k = 2 * k + 1 return min(k - self.num, self.n) def bisect_right(self, x): if self.mx[1] <= x: return self.n k = 1 while k < self.num: self.lazy_push(k) if self.mx[2 * k] > x: k *= 2 else: k = 2 * k + 1 return min(k - self.num, self.n) #遅延セグ木（区間更新用） class LazySegTree_RUQ: def __init__(self, init_val, segfunc, ide_ele): n = len(init_val) self.n = n self.segfunc = segfunc self.ide_ele = ide_ele self.num = 1 while self.num < n: self.num <<= 1 self.tree = [ide_ele] * (2 * self.num) # lazyの値 self.lazy = [0] * (2 * self.num) # そのノードに区間代入が存在するか self.lazy_flag = [False] * (2 * self.num) # bisect用の区間最大値 self.mx = [0] * (2 * self.num) for i in range(n): self.tree[self.num + i] = init_val[i] self.mx[self.num + i] = init_val[i] # num以降のダミー部分 for i in range(n, self.num): self.mx[self.num + i] = -10**30 for i in range(self.num - 1, 0, -1): self.tree[i] = self.segfunc( self.tree[2 * i], self.tree[2 * i + 1] ) self.mx[i] = max( self.mx[2 * i], self.mx[2 * i + 1] ) def gindex(self, l, r): l += self.num r += self.num low_l = l & -l low_r = r & -r lm = (l // low_l) // 2 * low_l rm = (r // low_r) // 2 * low_r while r > l: if l <= lm: yield l if r <= rm: yield r l >>= 1 r >>= 1 while l: yield l l >>= 1 def propagates(self, *ids): for i in reversed(ids): if not self.lazy_flag[i]: continue v = self.lazy[i] self.lazy_flag[i] = False self.lazy[2 * i] = v self.lazy[2 * i + 1] = v self.lazy_flag[2 * i] = True self.lazy_flag[2 * i + 1] = True self.tree[2 * i] = v self.tree[2 * i + 1] = v self.mx[2 * i] = v self.mx[2 * i + 1] = v def lazy_push(self, k): if not self.lazy_flag[k]: return v = self.lazy[k] self.lazy_flag[k] = False self.lazy[2 * k] = v self.lazy[2 * k + 1] = v self.lazy_flag[2 * k] = True self.lazy_flag[2 * k + 1] = True self.tree[2 * k] = v self.tree[2 * k + 1] = v self.mx[2 * k] = v self.mx[2 * k + 1] = v def update(self, l, r, x): ids = self.gindex(l, r) l += self.num r += self.num while l < r: if l & 1: self.lazy[l] = x self.lazy_flag[l] = True self.tree[l] = x self.mx[l] = x l += 1 if r & 1: r -= 1 self.lazy[r] = x self.lazy_flag[r] = True self.tree[r] = x self.mx[r] = x l >>= 1 r >>= 1 for i in ids: if i == 0: continue if self.lazy_flag[i]: self.tree[i] = self.lazy[i] self.mx[i] = self.lazy[i] else: self.tree[i] = self.segfunc( self.tree[2 * i], self.tree[2 * i + 1] ) self.mx[i] = max( self.mx[2 * i], self.mx[2 * i + 1] ) def query(self, l, r): self.propagates(*self.gindex(l, r)) res = self.ide_ele l += self.num r += self.num while l < r: if l & 1: res = self.segfunc(res, self.tree[l]) l += 1 if r & 1: res = self.segfunc(res, self.tree[r - 1]) l >>= 1 r >>= 1 return res def bisect_left(self, x): """ x 以上になる最初の位置 O(log N) 配列が単調非減少であることが必要。 """ if self.n == 0: return 0 if self.mx[1] < x: return self.n k = 1 while k < self.num: self.lazy_push(k) if self.mx[2 * k] >= x: k *= 2 else: k = 2 * k + 1 ans = k - self.num if ans >= self.n: return self.n return ans def bisect_right(self, x): """ x より大きくなる最初の位置 O(log N) 配列が単調非減少であることが必要。 """ if self.n == 0: return 0 if self.mx[1] <= x: return self.n k = 1 while k < self.num: self.lazy_push(k) if self.mx[2 * k] > x: k *= 2 else: k = 2 * k + 1 ans = k - self.num if ans >= self.n: return self.n return ans #FunctionalGraph（ダブリングなど） class FunctionalGraph: def __init__(self, n: int, next: list[int]) -> None: self.n = n self.sqrt_n = int(n**0.5) self.nexts = next self.jumps = [-1] * self.n self.visited = [False] * self.n self.cycles = [-1] * self.n self.cycles_index = [-1] * self.n self.calc_cycles() self.calc_jumps() def calc_jumps(self) -> None: for s in range(self.n): now = s for _ in range(self.sqrt_n): now = next[now] self.jumps[s] = now def calc_cycles(self) -> None: for s in range(self.n): if not self.visited[s]: path, cycle = self.dfs(s) for i, v in enumerate(cycle): self.cycles[v] = cycle self.cycles_index[v] = i def dfs(self, s: int) -> tuple[list[int], list[int]]: stack = [s] path = [s] cycle = [] self.visited[s] = True while stack: now = stack.pop() next = self.nexts[now] if not self.visited[next]: stack.append(next) self.visited[next] = True path.append(next) next = self.nexts[path[-1]] index = 0 while index < len(path): if path[index] == next: path, cycle = path[:index], path[index:] break index += 1 return path, cycle def get_next(self, s: int, k: int) -> int: now = s while self.cycles[now] == -1 and k > 0: if k >= self.sqrt_n: k -= self.sqrt_n now = self.jumps[now] else: k -= 1 now = self.nexts[now] if k == 0: return now cycle_len = len(self.cycles[now]) now = self.cycles[now][(self.cycles_index[now] + k) % cycle_len] return now #https://qiita.com/Shirotsume/items/706742162db68c481c3c #SortedList（挿入と二分探索がΘ(logn)) class SortedList: def __init__(self,n=20): if not 1<=n<=20:#0~1,048,575 print('Error: not 1<=n<=20', file=sys.stderr) sys.exit(1) self.n=n self.b=[] for i in range(self.n+1): self.b.append([0 for j in range(2**i)]) def __len__(self): return self.b[0][0] def __contains__(self,x): if not 0<=x<2**self.n: print('Error: not 0<=x<2**n', file=sys.stderr) sys.exit(1) return 0!=self.b[self.n][x] def __getitem__(self,x): if not 0<=x=self.b[0][0]: raise StopIteration return self.__getitem__(self._a) def insert(self,x): if not 0<=x<2**self.n: print('Error: not 0<=x<2**n', file=sys.stderr) sys.exit(1) for i in range(self.n+1): self.b[i][x//(2**(self.n-i))]+=1 def eject(self,x): if not 0<=x<2**self.n: print('Error: not 0<=x<2**n', file=sys.stderr) sys.exit(1) if not self.__contains__(x): print('Error: not x in', file=sys.stderr) sys.exit(1) for i in range(self.n+1): self.b[i][x//(2**(self.n-i))]-=1 def pop(self,x=0): p=self.__getitem__(x) self.eject(p) return p def remove(self,x): a=self.b[self.n][x] for i in range(self.n+1): self.b[i][x//(2**(self.n-i))]-=a def min(self,x=None): if x==None: x=-1 elif x>=2**self.n-1: return None elif x<0: x=-1 for i in range(self.n): if self.b[self.n-i][x//(2**i)+1]: a=x//(2**i)+1 for j in reversed(range(i)): if self.b[self.n-j][2*a]: a=2*a else: a=2*a+1 return a def max(self,x=None): if x==None: x=2**self.n elif x<=0: return None elif 2**self.n<=x: x=2**self.n for i in range(self.n): if self.b[self.n-i][x//(2**i)-1]: a=x//(2**i)-1 for j in reversed(range(i)): if self.b[self.n-j][2*a+1]: a=2*a+1 else: a=2*a return a def bisect_left(self,x): if not 0<=x<2**self.n: print('Error: not 0<=x<2**n', file=sys.stderr) sys.exit(1) a=0 for i in range(self.n): if x%2==1: a+=self.b[self.n-i][x-1] x=x//2 return a def bisect_right(self,x): if not 0<=x<2**self.n: print('Error: not 0<=x<2**n', file=sys.stderr) sys.exit(1) return self.bisect_left(x)+self.b[self.n][x] #SortedSet import math from bisect import bisect_left, bisect_right from typing import Generic, Iterable, Iterator, TypeVar T = TypeVar('T') class SortedSet(Generic[T]): BUCKET_RATIO = 16 SPLIT_RATIO = 24 def __init__(self, a: Iterable[T] = []) -> None: "Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)" a = list(a) n = len(a) if any(a[i] > a[i + 1] for i in range(n - 1)): a.sort() if any(a[i] >= a[i + 1] for i in range(n - 1)): a, b = [], a for x in b: if not a or a[-1] != x: a.append(x) n = self.size = len(a) num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO))) self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)] def __iter__(self) -> Iterator[T]: for i in self.a: for j in i: yield j def __reversed__(self) -> Iterator[T]: for i in reversed(self.a): for j in reversed(i): yield j def __eq__(self, other) -> bool: return list(self) == list(other) def __len__(self) -> int: return self.size def __repr__(self) -> str: return "SortedSet" + str(self.a) def __str__(self) -> str: s = str(list(self)) return "{" + s[1 : len(s) - 1] + "}" def _position(self, x: T) -> tuple[list[T], int, int]: "return the bucket, index of the bucket and position in which x should be. self must not be empty." for i, a in enumerate(self.a): if x <= a[-1]: break return (a, i, bisect_left(a, x)) def __contains__(self, x: T) -> bool: if self.size == 0: return False a, _, i = self._position(x) return i != len(a) and a[i] == x def add(self, x: T) -> bool: "Add an element and return True if added. / O(√N)" if self.size == 0: self.a = [[x]] self.size = 1 return True a, b, i = self._position(x) if i != len(a) and a[i] == x: return False a.insert(i, x) self.size += 1 if len(a) > len(self.a) * self.SPLIT_RATIO: mid = len(a) >> 1 self.a[b:b+1] = [a[:mid], a[mid:]] return True def _pop(self, a: list[T], b: int, i: int) -> T: ans = a.pop(i) self.size -= 1 if not a: del self.a[b] return ans def discard(self, x: T) -> bool: "Remove an element and return True if removed. / O(√N)" if self.size == 0: return False a, b, i = self._position(x) if i == len(a) or a[i] != x: return False self._pop(a, b, i) return True def lt(self, x: T) -> T | None: "Find the largest element < x, or None if it doesn't exist." for a in reversed(self.a): if a[0] < x: return a[bisect_left(a, x) - 1] def le(self, x: T) -> T | None: "Find the largest element <= x, or None if it doesn't exist." for a in reversed(self.a): if a[0] <= x: return a[bisect_right(a, x) - 1] def gt(self, x: T) -> T | None: "Find the smallest element > x, or None if it doesn't exist." for a in self.a: if a[-1] > x: return a[bisect_right(a, x)] def ge(self, x: T) -> T | None: "Find the smallest element >= x, or None if it doesn't exist." for a in self.a: if a[-1] >= x: return a[bisect_left(a, x)] def __getitem__(self, i: int) -> T: "Return the i-th element." if i < 0: for a in reversed(self.a): i += len(a) if i >= 0: return a[i] else: for a in self.a: if i < len(a): return a[i] i -= len(a) raise IndexError def pop(self, i: int = -1) -> T: "Pop and return the i-th element." if i < 0: for b, a in enumerate(reversed(self.a)): i += len(a) if i >= 0: return self._pop(a, ~b, i) else: for b, a in enumerate(self.a): if i < len(a): return self._pop(a, b, i) i -= len(a) raise IndexError def index(self, x: T) -> int: "Count the number of elements < x." ans = 0 for a in self.a: if a[-1] >= x: return ans + bisect_left(a, x) ans += len(a) return ans def index_right(self, x: T) -> int: "Count the number of elements <= x." ans = 0 for a in self.a: if a[-1] > x: return ans + bisect_right(a, x) ans += len(a) return ans #LCA(!!!sysで再帰上限を上げるように!!!) import sys sys.setrecursionlimit(6*10**5) class LCAFinder: def __init__(self, graph, root): self.n = len(graph) self.log = (self.n - 1).bit_length() self.parent = [[-1] * self.log for _ in range(self.n)] self.depth = [-1] * self.n # 木の深さと1つ上の親をDFSで計算 self.dfs(graph, root, -1, 0) # 倍増テーブルを構築 for j in range(1, self.log): for i in range(self.n): if self.parent[i][j - 1] != -1: self.parent[i][j] = self.parent[self.parent[i][j - 1]][j - 1] def dfs(self, graph, node, parent, depth): self.parent[node][0] = parent # 1つ上の親 self.depth[node] = depth for child in graph[node]: if child != parent: # 再訪防止 self.dfs(graph, child, node, depth + 1) def lca(self, u, v): # 深さを同じにする if self.depth[u] < self.depth[v]: u, v = v, u diff = self.depth[u] - self.depth[v] for i in range(self.log): if diff & (1 << i): u = self.parent[u][i] # 同じノードになれば終了 if u == v: return u # 上から二分探索で LCA を探す for i in range(self.log - 1, -1, -1): if self.parent[u][i] != self.parent[v][i]: u = self.parent[u][i] v = self.parent[v][i] return self.parent[u][0] #FFT（畳み込み） class FFT(): def primitive_root_constexpr(self, m): if m == 2: return 1 if m == 167772161: return 3 if m == 469762049: return 3 if m == 754974721: return 11 if m == 998244353: return 3 divs = [0] * 20 divs[0] = 2 cnt = 1 x = (m - 1) // 2 while (x % 2 == 0): x //= 2 i = 3 while (i * i <= x): if (x % i == 0): divs[cnt] = i cnt += 1 while (x % i == 0): x //= i i += 2 if x > 1: divs[cnt] = x cnt += 1 g = 2 while (1): ok = True for i in range(cnt): if pow(g, (m - 1) // divs[i], m) == 1: ok = False break if ok: return g g += 1 def bsf(self, x): res = 0 while (x % 2 == 0): res += 1 x //= 2 return res rank2 = 0 root = [] iroot = [] rate2 = [] irate2 = [] rate3 = [] irate3 = [] def __init__(self, MOD): self.mod = MOD self.g = self.primitive_root_constexpr(self.mod) self.rank2 = self.bsf(self.mod - 1) self.root = [0 for i in range(self.rank2 + 1)] self.iroot = [0 for i in range(self.rank2 + 1)] self.rate2 = [0 for i in range(self.rank2)] self.irate2 = [0 for i in range(self.rank2)] self.rate3 = [0 for i in range(self.rank2 - 1)] self.irate3 = [0 for i in range(self.rank2 - 1)] self.root[self.rank2] = pow(self.g, (self.mod - 1) >> self.rank2, self.mod) self.iroot[self.rank2] = pow(self.root[self.rank2], self.mod - 2, self.mod) for i in range(self.rank2 - 1, -1, -1): self.root[i] = (self.root[i + 1] ** 2) % self.mod self.iroot[i] = (self.iroot[i + 1] ** 2) % self.mod prod = 1; iprod = 1 for i in range(self.rank2 - 1): self.rate2[i] = (self.root[i + 2] * prod) % self.mod self.irate2[i] = (self.iroot[i + 2] * iprod) % self.mod prod = (prod * self.iroot[i + 2]) % self.mod iprod = (iprod * self.root[i + 2]) % self.mod prod = 1; iprod = 1 for i in range(self.rank2 - 2): self.rate3[i] = (self.root[i + 3] * prod) % self.mod self.irate3[i] = (self.iroot[i + 3] * iprod) % self.mod prod = (prod * self.iroot[i + 3]) % self.mod iprod = (iprod * self.root[i + 3]) % self.mod def butterfly(self, a): n = len(a) h = (n - 1).bit_length() LEN = 0 while (LEN < h): if (h - LEN == 1): p = 1 << (h - LEN - 1) rot = 1 for s in range(1 << LEN): offset = s << (h - LEN) for i in range(p): l = a[i + offset] r = a[i + offset + p] * rot a[i + offset] = (l + r) % self.mod a[i + offset + p] = (l - r) % self.mod rot *= self.rate2[(~s & -~s).bit_length() - 1] rot %= self.mod LEN += 1 else: p = 1 << (h - LEN - 2) rot = 1 imag = self.root[2] for s in range(1 << LEN): rot2 = (rot * rot) % self.mod rot3 = (rot2 * rot) % self.mod offset = s << (h - LEN) for i in range(p): a0 = a[i + offset] a1 = a[i + offset + p] * rot a2 = a[i + offset + 2 * p] * rot2 a3 = a[i + offset + 3 * p] * rot3 a1na3imag = (a1 - a3) % self.mod * imag a[i + offset] = (a0 + a2 + a1 + a3) % self.mod a[i + offset + p] = (a0 + a2 - a1 - a3) % self.mod a[i + offset + 2 * p] = ( a0 - a2 + a1na3imag) % self.mod a[i + offset + 3 * p] = ( a0 - a2 - a1na3imag) % self.mod rot *= self.rate3[(~s & -~s).bit_length() - 1] rot %= self.mod LEN += 2 def butterfly_inv(self, a): n = len(a) h = (n - 1).bit_length() LEN = h while (LEN): if (LEN == 1): p = 1 << (h - LEN) irot = 1 for s in range(1 << (LEN - 1)): offset = s << (h - LEN + 1) for i in range(p): l = a[i + offset] r = a[i + offset + p] a[i + offset] = (l + r) % self.mod a[i + offset + p] = (l - r) * irot % self.mod irot *= self.irate2[(~s & -~s).bit_length() - 1] irot %= self.mod LEN -= 1 else: p = 1 << (h - LEN) irot = 1 iimag = self.iroot[2] for s in range(1 << (LEN - 2)): irot2 = (irot * irot) % self.mod irot3 = (irot * irot2) % self.mod offset = s << (h - LEN + 2) for i in range(p): a0 = a[i + offset] a1 = a[i + offset + p] a2 = a[i + offset + 2 * p] a3 = a[i + offset + 3 * p] a2na3iimag = (a2 - a3) * iimag % self.mod a[i + offset] = (a0 + a1 + a2 + a3) % self.mod a[i + offset + p] = ( a0 - a1 + a2na3iimag) * irot % self.mod a[i + offset + 2 * p] = ( a0 + a1 - a2 - a3) * irot2 % self.mod a[i + offset + 3 * p] = ( a0 - a1 - a2na3iimag) * irot3 % self.mod irot *= self.irate3[(~s & -~s).bit_length() - 1] irot %= self.mod LEN -= 2 def convolution(self, a, b): n = len(a); m = len(b) if not (a) or not (b): return [] if min(n, m) <= 40: res = [0] * (n + m - 1) for i in range(n): for j in range(m): res[i + j] += a[i] * b[j] res[i + j] %= self.mod return res z = 1 << ((n + m - 2).bit_length()) a = a + [0] * (z - n) b = b + [0] * (z - m) self.butterfly(a) self.butterfly(b) c = [(a[i] * b[i]) % self.mod for i in range(z)] self.butterfly_inv(c) iz = pow(z, self.mod - 2, self.mod) for i in range(n + m - 1): c[i] = (c[i] * iz) % self.mod return c[:n + m - 1] #merge-sort-tree ''' ある区間のある値以下の個数を求める ''' from bisect import bisect from heapq import merge def construct(N, A): N0 = 2**(N-1).bit_length() data = [None]*(2*N0) for i, a in enumerate(A): data[N0-1+i] = [a] for i in range(N, N0): data[N0-1+i] = [] for i in range(N0-2, -1, -1): *data[i], = merge(data[2*i+1], data[2*i+2]) return N0, data # count elements A_i s.t. A_i <= k for i in [l, r) def query1(N0, data, l, r, k): L = l + N0; R = r + N0 s = 0 while L < R: if R & 1: R -= 1 s += bisect(data[R-1], k-1) if L & 1: s += bisect(data[L-1], k-1) L += 1 L >>= 1; R >>= 1 return s # count elements A_i s.t. a <= A_i < b for i in [l, r) def query(N0, data, l, r, a, b): L = l + N0; R = r + N0 s = 0 while L < R: if R & 1: R -= 1 s += bisect(data[R-1], b-1) - bisect(data[R-1], a-1) if L & 1: s += bisect(data[L-1], b-1) - bisect(data[L-1], a-1) L += 1 L >>= 1; R >>= 1 return s #双連結リスト import heapq class DoublyLinkedList: class Node: def __init__(self, x): self.value = x self.left = -1 self.right = -1 self.alive = True def __init__(self, A): N = len(A) self.nodes = [self.Node(x) for x in A] for i in range(N): if i > 0: self.nodes[i].left = i - 1 if i + 1 < N: self.nodes[i].right = i + 1 def left(self, i): return self.nodes[i].left def right(self, i): return self.nodes[i].right def get(self, i): return self.nodes[i].value def set(self, i, x): self.nodes[i].value = x def erase(self, i): L = self.nodes[i].left R = self.nodes[i].right if L != -1: self.nodes[L].right = R if R != -1: self.nodes[R].left = L self.nodes[i].alive = False self.nodes[i].left = -1 self.nodes[i].right = -1 def insert(self, i, x, L, R): self.nodes[i].value = x self.nodes[i].left = L self.nodes[i].right = R self.nodes[i].alive = True if L != -1: self.nodes[L].right = i if R != -1: self.nodes[R].left = i #Treap(区間加算、区間更新) import random class ImplicitTreap: def __init__(self): # 0 = null self.val = [0] self.sum = [0] self.cnt = [0] self.pri = [0] self.left = [0] self.right = [0] # lazy add self.lazy_add = [0] # lazy assign self.lazy_set = [0] self.has_set = [False] # lazy reverse self.rev = [False] self.root = 0 # ========================================================= # 基本 # ========================================================= def size(self): """要素数を返す。O(1)""" return self.cnt[self.root] # ========================================================= # ノード生成 # ========================================================= def new_node(self, x): t = len(self.val) self.val.append(x) self.sum.append(x) self.cnt.append(1) self.pri.append( random.randint(1, 2147483647) ) self.left.append(0) self.right.append(0) self.lazy_add.append(0) self.lazy_set.append(0) self.has_set.append(False) self.rev.append(False) return t # ========================================================= # 区間代入 # # 部分木 t 全体を x にする # ========================================================= def apply_set(self, t, x): if t == 0: return self.val[t] = x self.sum[t] = x * self.cnt[t] self.lazy_add[t] = 0 self.lazy_set[t] = x self.has_set[t] = True # ========================================================= # 区間加算 # ========================================================= def apply_add(self, t, x): if t == 0: return self.val[t] += x self.sum[t] += x * self.cnt[t] if self.has_set[t]: self.lazy_set[t] += x else: self.lazy_add[t] += x # ========================================================= # 区間反転 # ========================================================= def apply_reverse(self, t): if t == 0: return self.left[t], self.right[t] = \ self.right[t], self.left[t] self.rev[t] = not self.rev[t] # ========================================================= # lazy propagation # ========================================================= def push(self, t): if t == 0: return l = self.left[t] r = self.right[t] if self.has_set[t]: x = self.lazy_set[t] self.apply_set(l, x) self.apply_set(r, x) self.has_set[t] = False if self.lazy_add[t] != 0: x = self.lazy_add[t] self.apply_add(l, x) self.apply_add(r, x) self.lazy_add[t] = 0 if self.rev[t]: self.apply_reverse(l) self.apply_reverse(r) self.rev[t] = False # ========================================================= # 情報更新 # ========================================================= def update(self, t): if t == 0: return l = self.left[t] r = self.right[t] self.cnt[t] = ( self.cnt[l] + 1 + self.cnt[r] ) self.sum[t] = ( self.sum[l] + self.val[t] + self.sum[r] ) # ========================================================= # split # # [0,k) | [k,n) # ========================================================= def split(self, t, k): if t == 0: return 0, 0 self.push(t) ls = self.cnt[self.left[t]] if k <= ls: a, b = self.split( self.left[t], k ) self.left[t] = b self.update(t) return a, t else: a, b = self.split( self.right[t], k - ls - 1 ) self.right[t] = a self.update(t) return t, b # ========================================================= # merge # ========================================================= def merge(self, a, b): if a == 0: return b if b == 0: return a if self.pri[a] > self.pri[b]: self.push(a) self.right[a] = self.merge( self.right[a], b ) self.update(a) return a else: self.push(b) self.left[b] = self.merge( a, self.left[b] ) self.update(b) return b # ========================================================= # insert # # p 番目に x を挿入 # ========================================================= def insert(self, p, x): a, b = self.split( self.root, p ) t = self.new_node(x) self.root = self.merge( self.merge(a, t), b ) # ========================================================= # get # # p 番目の要素を取得する。削除しない。 # ========================================================= def get(self, p): a, b = self.split( self.root, p ) c, d = self.split( b, 1 ) self.push(c) ans = self.val[c] self.root = self.merge( a, self.merge(c, d) ) return ans # ========================================================= # pop # # p 番目の要素を削除して、その値を返す。 # p=-1 なら末尾。 # ========================================================= def pop(self, p=-1): n = self.size() if p < 0: p += n a, b = self.split( self.root, p ) c, d = self.split( b, 1 ) self.push(c) ans = self.val[c] self.root = self.merge( a, d ) return ans # ========================================================= # erase # # p 番目の要素を削除する。 # ========================================================= def erase(self, p): a, b = self.split( self.root, p ) c, d = self.split( b, 1 ) self.root = self.merge( a, d ) # ========================================================= # discard # # p 番目の要素を削除する。 # 範囲外なら何もしない。 # ========================================================= def discard(self, p): n = self.size() if p < 0: p += n if p < 0 or p >= n: return a, b = self.split( self.root, p ) c, d = self.split( b, 1 ) self.root = self.merge( a, d ) # ========================================================= # reverse [l,r) # ========================================================= def reverse(self, l, r): a, b = self.split( self.root, l ) c, d = self.split( b, r - l ) self.apply_reverse(c) self.root = self.merge( a, self.merge(c, d) ) # ========================================================= # 区間加算 [l,r) # # a[i] += x # ========================================================= def apply(self, l, r, x): a, b = self.split( self.root, l ) c, d = self.split( b, r - l ) self.apply_add(c, x) self.root = self.merge( a, self.merge(c, d) ) # ========================================================= # 区間代入 [l,r) # # a[i] = x # ========================================================= def assign(self, l, r, x): a, b = self.split( self.root, l ) c, d = self.split( b, r - l ) self.apply_set(c, x) self.root = self.merge( a, self.merge(c, d) ) # ========================================================= # 区間和 [l,r) # ========================================================= def prod(self, l, r): a, b = self.split( self.root, l ) c, d = self.split( b, r - l ) ans = self.sum[c] self.root = self.merge( a, self.merge(c, d) ) return ans # ========================================================= # 配列化 # ========================================================= def to_list(self): res = [] stack = [] t = self.root while stack or t != 0: while t != 0: self.push(t) stack.append(t) t = self.left[t] t = stack.pop() res.append(self.val[t]) t = self.right[t] return res #Treap (区間がsortされている前提で、bisect,insortがlog_n) import random class Treap: def __init__(self, arr): # node 0 = null node self.val = [0] self.priority = [0] self.left = [0] self.right = [0] self.size_ = [0] self.sum_ = [0] self.root = 0 for x in arr: self.insert(x) # ========================================== # 基本 # ========================================== def size(self): return self.size_[self.root] def _size(self, t): return self.size_[t] def _sum(self, t): return self.sum_[t] def _update(self, t): self.size_[t] = ( 1 + self.size_[self.left[t]] + self.size_[self.right[t]] ) self.sum_[t] = ( self.val[t] + self.sum_[self.left[t]] + self.sum_[self.right[t]] ) # ========================================== # node 作成 # ========================================== def _new_node(self, x): idx = len(self.val) self.val.append(x) self.priority.append(random.randint(0, 2147483647)) self.left.append(0) self.right.append(0) self.size_.append(1) self.sum_.append(x) return idx # ========================================== # split # # x 以下 | x より大きい # # equal が False の場合： # x 未満 | x 以上 # ========================================== def _split_le(self, t, x): if t == 0: return 0, 0 if self.val[t] <= x: a, b = self._split_le(self.right[t], x) self.right[t] = a self._update(t) return t, b else: a, b = self._split_le(self.left[t], x) self.left[t] = b self._update(t) return a, t def _split_lt(self, t, x): if t == 0: return 0, 0 if self.val[t] < x: a, b = self._split_lt(self.right[t], x) self.right[t] = a self._update(t) return t, b else: a, b = self._split_lt(self.left[t], x) self.left[t] = b self._update(t) return a, t # ========================================== # merge # ========================================== def _merge(self, a, b): if a == 0: return b if b == 0: return a if self.priority[a] > self.priority[b]: self.right[a] = self._merge( self.right[a], b ) self._update(a) return a else: self.left[b] = self._merge( a, self.left[b] ) self._update(b) return b # ========================================== # insert # ========================================== def insert(self, x): node = self._new_node(x) # x 以下 | x より大きい a, b = self._split_le(self.root, x) self.root = self._merge( self._merge(a, node), b ) # ========================================== # bisect_left # # x 以上の最初の位置 # # 例： # [1, 2, 2, 5] # # bisect_left(2) = 1 # ========================================== def bisect_left(self, x): t = self.root ans = 0 while t != 0: if self.val[t] >= x: t = self.left[t] else: ans += 1 + self.size_[self.left[t]] t = self.right[t] return ans # ========================================== # bisect_right # # x より大きい最初の位置 # # 例： # [1, 2, 2, 5] # # bisect_right(2) = 3 # ========================================== def bisect_right(self, x): t = self.root ans = 0 while t != 0: if self.val[t] > x: t = self.left[t] else: ans += 1 + self.size_[self.left[t]] t = self.right[t] return ans # ========================================== # sum_prefix # # x 未満の要素の総和 # # 例： # [1, 2, 2, 5] # # sum_prefix(5) = 5 # ========================================== def sum_prefix(self, x): t = self.root ans = 0 while t != 0: if self.val[t] >= x: t = self.left[t] else: ans += ( self.sum_[self.left[t]] + self.val[t] ) t = self.right[t] return ans # ========================================== # sum_prefix_right # # x 以下の要素の総和 # ========================================== def sum_prefix_right(self, x): t = self.root ans = 0 while t != 0: if self.val[t] > x: t = self.left[t] else: ans += ( self.sum_[self.left[t]] + self.val[t] ) t = self.right[t] return ans # ========================================== # prod # # 値 l <= x < r の総和 # # 例： # [1, 2, 2, 4, 5, 7] # # prod(2, 7) # # = 2 + 2 + 4 + 5 # = 13 # ========================================== def prod(self, l, r): return ( self.sum_prefix(r) - self.sum_prefix(l) ) # ========================================== # get # # ソート順で i 番目の値 # ========================================== def get(self, i): t = self.root while t != 0: ls = self.size_[self.left[t]] if i < ls: t = self.left[t] elif i == ls: return self.val[t] else: i -= ls + 1 t = self.right[t] return 0 # ========================================== # erase_one # # x を1個削除 # ========================================== def erase_one(self, x): a, b = self._split_lt(self.root, x) c, d = self._split_le(b, x) # c の中から1個削除 # c が空なら何もしない if c != 0: c = self._erase_root(c) self.root = self._merge( a, self._merge(c, d) ) def _erase_root(self, t): return self._merge( self.left[t], self.right[t] ) # ========================================== # 全要素取得 # ========================================== def to_list(self): res = [] stack = [] t = self.root while stack or t != 0: while t != 0: stack.append(t) t = self.left[t] t = stack.pop() res.append(self.val[t]) t = self.right[t] return res #任意のモノイドを乗せられるTreap # ========================================================= # Implicit Treap # # 任意のオブジェクトを要素として持つ # # 例: # ["ab", "ac", "d", "bcd"] # # 対応操作: # # insert(p, x) : p番目にxを挿入 # get(p) : p番目を取得 # pop(p) : p番目を削除して返す # erase(p) : p番目を削除 # reverse(l, r) : [l,r) を反転 # to_list() : 全体をリストとして取得 # size() : 要素数 # build(arr) : 配列から構築 # # insert / get / pop / erase / reverse # 期待 O(log N) # # to_list # O(N) # # 区間積・区間和などの情報は一切持たない # ========================================================= import random class ImplicitTreap: def __init__(self): # 0 = null self.val = [None] self.cnt = [0] self.pri = [0] self.left = [0] self.right = [0] # lazy reverse self.rev = [False] self.root = 0 # ========================================================= # size # ========================================================= def size(self): return self.cnt[self.root] # ========================================================= # new node # ========================================================= def new_node(self, x): t = len(self.val) self.val.append(x) self.cnt.append(1) self.pri.append( random.randint(1, 2147483647) ) self.left.append(0) self.right.append(0) self.rev.append(False) return t # ========================================================= # apply reverse # # 部分木全体を反転 # ========================================================= def apply_reverse(self, t): if t == 0: return self.left[t], self.right[t] = \ self.right[t], self.left[t] self.rev[t] = not self.rev[t] # ========================================================= # push # ========================================================= def push(self, t): if t == 0: return if self.rev[t]: self.apply_reverse( self.left[t] ) self.apply_reverse( self.right[t] ) self.rev[t] = False # ========================================================= # update # ========================================================= def update(self, t): if t == 0: return l = self.left[t] r = self.right[t] self.cnt[t] = ( self.cnt[l] + 1 + self.cnt[r] ) # ========================================================= # split # # [0,k) | [k,n) # ========================================================= def split(self, t, k): if t == 0: return 0, 0 self.push(t) ls = self.cnt[self.left[t]] if k <= ls: a, b = self.split( self.left[t], k ) self.left[t] = b self.update(t) return a, t else: a, b = self.split( self.right[t], k - ls - 1 ) self.right[t] = a self.update(t) return t, b # ========================================================= # merge # ========================================================= def merge(self, a, b): if a == 0: return b if b == 0: return a if self.pri[a] > self.pri[b]: self.push(a) self.right[a] = self.merge( self.right[a], b ) self.update(a) return a else: self.push(b) self.left[b] = self.merge( a, self.left[b] ) self.update(b) return b # ========================================================= # insert # # p番目の前に x を挿入 # # ["a","b","c"] # insert(1,"X") # # -> ["a","X","b","c"] # ========================================================= def insert(self, p, x): a, b = self.split( self.root, p ) t = self.new_node(x) self.root = self.merge( self.merge(a, t), b ) # ========================================================= # get # # p番目の要素を取得 # ========================================================= def get(self, p): a, b = self.split( self.root, p ) c, d = self.split( b, 1 ) self.push(c) ans = self.val[c] self.root = self.merge( a, self.merge(c, d) ) return ans # ========================================================= # pop # # p番目を削除して返す # # p=-1 なら末尾 # ========================================================= def pop(self, p=-1): n = self.size() if p < 0: p += n a, b = self.split( self.root, p ) c, d = self.split( b, 1 ) self.push(c) ans = self.val[c] self.root = self.merge( a, d ) return ans # ========================================================= # erase # # p番目を削除 # ========================================================= def erase(self, p): a, b = self.split( self.root, p ) c, d = self.split( b, 1 ) self.root = self.merge( a, d ) # ========================================================= # reverse # # [l,r) を反転 # ========================================================= def reverse(self, l, r): a, b = self.split( self.root, l ) c, d = self.split( b, r - l ) self.apply_reverse(c) self.root = self.merge( a, self.merge(c, d) ) # ========================================================= # to_list # ========================================================= def to_list(self): res = [] stack = [] t = self.root while stack or t != 0: while t != 0: self.push(t) stack.append(t) t = self.left[t] t = stack.pop() res.append( self.val[t] ) t = self.right[t] return res # ========================================================= # build # # arr からTreapを構築 # ========================================================= def build(self, arr): self.root = 0 for x in arr: t = self.new_node(x) self.root = self.merge( self.root, t )