・再帰
import sys
sys.setrecursionlimit(10**6)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')

デコレータ
from types import GeneratorType

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
            else:
                stack.pop()
                if not stack:
                    break
                to = stack[-1].send(to)
        return to
    return wrappedfunc
〇使い方
1. @bootstrap を再帰関数の前につける
2. returnはyieldと書く
3. 自身を呼び出す場合は先頭にyieldと書く（計算式の中などで呼び出す場合は括弧で囲む [(yield func(a))]）
4. 戻り値がない場合でも、最後にyieldと書く
5. 再帰上限の変更は書く必要がない

・実行速度の計測
import time
start = time.time()
end = time.time()
print(end - start)

・UnionFind
class UnionFind:
    def __init__(self,n):
        self.n = n
        self.parent_size = [-1]*n
 
    def leader(self,a):
        if self.parent_size[a] < 0:
            return a
        self.parent_size[a] = self.leader(self.parent_size[a])
        return self.parent_size[a]
 
    def merge(self,a,b):
        x, y = self.leader(a), self.leader(b)
        if x == y:
            return 
        if abs(self.parent_size[x]) < abs(self.parent_size[y]):
            x, y = y, x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y] = x
        return 
 
    def same(self,a,b):
        return self.leader(a) == self.leader(b)
 
    def size(self,a):
        return abs(self.parent_size[self.leader(a)])
 
    def groups(self):
        result = [[] for _ in range(self.n)]
        for i in range(self.n):
            result[self.leader(i)].append(i)
        return [r for r in result if r != []]

・素数判定
def isPrime(n):
    if n <= 1:
        return False
    else:
        i = 2
        while i**2 <= n:
            if n%i == 0:
                return False
            i += 1
        return True

・エラトステネスのふるい
def eratosthenes(n):
    sieve = [True] * (n + 1)
    for i in range(int(n**0.5) + 1):
        if i < 2:
            sieve[i] = False
        elif sieve[i]:
            for j in range(i, n//i + 1):
                sieve[i * j] = False
    ans = []
    for i in range(n+1):
        if sieve[i]:
            ans.append(i)
    return ans

・10進数→n進数
def base_n(num_10,n):
    str_n = ''
    while num_10:
        if num_10%n>=10:
            return -1
        str_n += str(num_10%n)
        num_10 //= n
    return int(str_n[::-1])

・ユークリッドの互除法
def gcd(a, b):
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b
    return b

・素因数分解
from math import isqrt

def factorization(n):
    arr = []
    temp = n
    for i in range(2, isqrt(n)+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr

・約数列挙
def divisor(n):
    ans = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ans.append(i)
            if i*i != n:
                ans.append(n//i)
    return ans

・２点間の距離
def distance(x1, y1, x2, y2):
    return ((x2-x1)**2 + (y2-y1)**2) ** 0.5
（比較演算をする場合はルートを外してかわりに反対側を2乗する）

・トリミング
def trimming(A):
    minH = len(A)
    maxH = 0
    minW = len(A[0])
    maxW = 0
    for i in range(len(A)):
        for j in range(len(A[0])):
            if A[i][j] == "#":
                minH = min(i, minH)
                maxH = max(i, maxH)
                minW = min(j, minW)
                maxW = max(j, maxW)
    a = []
    for i in range(minH, maxH+1):
        a.append(A[i][minW:maxW+1])
    return a

・回転（時計回り）
def rotateR(A):
    return list(map(list, zip(*A[::-1])))

・回転（反時計回り）
def rotateL(A):
    return list(map(list, zip(*A)))[::-1]

・ランダムアクセスがO(1)のdeque
class Deque:
    def __init__(self, src_arr=[], max_size=300000):
        self.N = max(max_size, len(src_arr)) + 1
        self.buf = list(src_arr) + [None] * (self.N - len(src_arr))
        self.head = 0
        self.tail = len(src_arr)
    def __index(self, i):
        l = len(self)
        if not -l <= i < l: raise IndexError('index out of range: ' + str(i))
        if i < 0:
            i += l
        return (self.head + i) % self.N
    def __extend(self):
        ex = self.N - 1
        self.buf[self.tail+1 : self.tail+1] = [None] * ex
        self.N = len(self.buf)
        if self.head > 0:
            self.head += ex
    def is_full(self):
        return len(self) >= self.N - 1
    def is_empty(self):
        return len(self) == 0
    def append(self, x):
        if self.is_full(): self.__extend()
        self.buf[self.tail] = x
        self.tail += 1
        self.tail %= self.N
    def appendleft(self, x):
        if self.is_full(): self.__extend()
        self.buf[(self.head - 1) % self.N] = x
        self.head -= 1
        self.head %= self.N
    def pop(self):
        if self.is_empty(): raise IndexError('pop() when buffer is empty')
        ret = self.buf[(self.tail - 1) % self.N]
        self.tail -= 1
        self.tail %= self.N
        return ret
    def popleft(self):
        if self.is_empty(): raise IndexError('popleft() when buffer is empty')
        ret = self.buf[self.head]
        self.head += 1
        self.head %= self.N
        return ret
    def __len__(self):
        return (self.tail - self.head) % self.N
    def __getitem__(self, key):
        return self.buf[self.__index(key)]
    def __setitem__(self, key, value):
        self.buf[self.__index(key)] = value
    def __str__(self):
        return 'Deque({0})'.format(str(list(self)))

・セグメント木
def op(x, y):
    return 
class SegTree:
    def __init__(self, init_val, op, ide_ele):
        n = len(init_val)
        self.n = n
        self.op = op
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        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.op(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            l, r = k, k^1
            if l > r:
                l, r = r, l
            self.tree[k >> 1] = self.op(self.tree[l], self.tree[r])
            k >>= 1

    def query(self, l, r):
        res_l = self.ide_ele
        res_r = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.tree[l])
                l += 1
            if r & 1:
                res_r = self.op(self.tree[r - 1], res_r)
            l >>= 1
            r >>= 1
        return self.op(res_l, res_r)

    def __getitem__(self, n):
        return self.tree[self.num+n]
    
    def List(self):
        return self.tree[self.num:self.num+self.n]
    
    def max_right(self, l, f, limit):
        if l == self.n:
            return self.n
        l += self.num
        sm = self.ide_ele
        while True:
            while l%2 == 0:
                l >>= 1
            if not f(self.op(sm, self.tree[l]), limit):
                while l < self.num:
                    l <<= 1
                    if f(self.op(sm, self.tree[l]), limit):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l-self.num
            sm = self.op(sm, self.tree[l])
            l += 1
            if l & -l == l:
                break
        return self.n
    
    def min_left(self, r, f, limit):
        if r == 0:
            return 0
        r += self.num
        sm = self.ide_ele
        while True:
            r -= 1
            while r > 1 and r%2 == 1:
                r >>= 1
            if not f(self.op(self.tree[r], sm), limit):
                while r < self.num:
                    r = 2*r+1
                    if f(self.op(self.tree[r], sm), limit):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r+1-self.num
            sm = self.op(self.tree[r], sm)
            if r & -r == r:
                break
        return 0
〇使い方
1. 初期化用のリストを用意
2. 区間に行う操作をsegfuncに書き込む
   ・最小値 min(x, y)
   ・最大値 max(x, y)
   ・区間和 x + y
   ・区間積 x * y
   ・最大公約数 math.gcd(x, y)
3. 生成
   seg = SegTree(リスト, segfunc, (単位元))
   ・単位元
     ・最小値 float('inf')
     ・最大値 -float('inf')
     ・区間和 0
     ・区間積 1
     ・最大公約数 0
4. 操作
   0-index
   ・更新
     seg.update(k, x) k番目の要素をxに更新
   ・区間の操作の結果を取得
     seg.query(l, r) l以上r未満の区間から値を取得

・ダイクストラ法
def dijkstra(start):
    INF = 10**18
    dist = [INF]*N
    dist[start] = 0
    visited = [False]*N
    que = [(0, start)]
    while que:
        d, now = heappop(que)
        if visited[now]:
            continue
        visited[now] = True
        for next, weight in G[now]:
            if dist[now]+weight < dist[next]:
                dist[next] = dist[now]+weight
                heappush(que, (dist[next], next))
    return dist

・Ford-Fulkerson
class maxflow_edge:
    def __init__(self, to, cap, rev):
        self.to = to
        self.cap = cap
        self.rev = rev

@bootstrap
def dfs(pos, goal, F, G, visited):
    if pos == goal:
        yield F
    visited[pos] = True
    for e in G[pos]:
        if not visited[e.to] and e.cap > 0:
            flow = yield dfs(e.to, goal, min(F, e.cap), G, visited)
            if flow >= 1:
                e.cap -= flow
                G[e.to][e.rev].cap += flow
                yield flow
    yield 0

def maxflow(s, t, N):
    G = [[] for i in range(N)]
    for a, b, c in edge:
        G[a].append(maxflow_edge(b, c, len(G[b])))
        G[b].append(maxflow_edge(a, 0, len(G[a])-1))
    total_flow = 0
    while True:
        visited = [False]*N
        F = dfs(s, t, INF, G, visited)
        if F > 0:
            total_flow += F
        else:
            break
    return total_flow

・逆元
def inverse(n, d):
    return n * pow(d, -1, MOD) % MOD

・遅延セグメント木
〇区間加算用
def segfunc(x,y):
    return 
class LazySegTree_RAQ:
    def __init__(self,init_val,segfunc,ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1<<(n-1).bit_length()
        self.tree = [ide_ele]*2*self.num
        self.lazy = [0]*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[2*i], self.tree[2*i+1])
    def gindex(self,l,r):
        l += self.num
        r += self.num
        lm = l>>(l&-l).bit_length()
        rm = r>>(r&-r).bit_length()
        ans = []
        while r>l:
            if l<=lm:
                ans.append(l)
            if r<=rm:
                ans.append(r)
            r >>= 1
            l >>= 1
        while l:
            ans.append(l)
            l >>= 1
        return ans
    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
    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
                l += 1
            if r&1:
                self.lazy[r-1] += x
                self.tree[r-1] += x
            r >>= 1
            l >>= 1
        for i in ids:
            self.tree[i] = self.segfunc(self.tree[2*i], self.tree[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 segfunc(x,y):
    return 
class LazySegTree_RUQ:
    def __init__(self,init_val,segfunc,ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1<<(n-1).bit_length()
        self.tree = [ide_ele]*2*self.num
        self.lazy = [None]*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[2*i],self.tree[2*i+1])
    def gindex(self,l,r):
        l += self.num
        r += self.num
        lm = l>>(l&-l).bit_length()
        rm = r>>(r&-r).bit_length()
        ans = []
        while r>l:
            if l<=lm:
                ans.append(l)
            if r<=rm:
                ans.append(r)
            r >>= 1
            l >>= 1
        while l:
            ans.append(l)
            l >>= 1
        return ans
    def propagates(self,ids):
        for i in reversed(ids):
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[i] = None
            self.lazy[2*i] = v
            self.lazy[2*i+1] = v
            self.tree[2*i] = v
            self.tree[2*i+1] = v
    def update(self,l,r,x):
        ids = self.gindex(l,r)
        self.propagates(ids)
        l += self.num
        r += self.num
        while l<r:
            if l&1:
                self.lazy[l] = x
                self.tree[l] = x
                l += 1
            if r&1:
                self.lazy[r-1] = x
                self.tree[r-1] = x
            r >>= 1
            l >>= 1
        for i in ids:
            self.tree[i] = self.segfunc(self.tree[2*i], self.tree[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
〇使い方
1. 初期化用のリストを用意
2. 区間に行う操作をsegfuncに書き込む
   ・最小値 min(x, y)
   ・最大値 max(x, y)
   ・区間和 x + y
   ・区間積 x * y
   ・最大公約数 math.gcd(x, y)
3. 生成
   seg = SegTree(リスト, segfunc, (単位元))
   ・単位元
     ・最小値 float('inf')
     ・最大値 -float('inf')
     ・区間和 0
     ・区間積 1
     ・最大公約数 0
4. 操作
   0-index
   ・更新
     seg.add(l, r, x) l以上r未満の区間にxを加算
     seg.update(l, r, x) l以上r未満の区間をxに更新
   ・区間の操作の結果を取得
     seg.query(l, r) l以上r未満の区間から値を取得

・素数リスト
18625498411672028939
93638244515503437017
15508888921625689043
桁最大の素数
1桁⋅⋅⋅7
2桁⋅⋅⋅97
3桁⋅⋅⋅997
4桁⋅⋅⋅9973
5桁⋅⋅⋅99991
6桁⋅⋅⋅999983
7桁⋅⋅⋅9999991
8桁⋅⋅⋅99999989
9桁⋅⋅⋅999999937
10桁⋅⋅⋅9999999967
11桁⋅⋅⋅99999999977
12桁⋅⋅⋅999999999989
13桁⋅⋅⋅9999999999971
14桁⋅⋅⋅99999999999973
15桁⋅⋅⋅999999999999989
16桁⋅⋅⋅9999999999999937
17桁⋅⋅⋅99999999999999997
18桁⋅⋅⋅999999999999999989
19桁⋅⋅⋅9999999999999999961
20桁⋅⋅⋅99999999999999999989
桁最小の素数
1桁⋅⋅⋅2
2桁⋅⋅⋅11
3桁⋅⋅⋅101
4桁⋅⋅⋅1009
5桁⋅⋅⋅10007
6桁⋅⋅⋅100003
7桁⋅⋅⋅1000003
8桁⋅⋅⋅10000019
9桁⋅⋅⋅100000007
10桁⋅⋅⋅1000000007
11桁⋅⋅⋅10000000019
12桁⋅⋅⋅100000000003
13桁⋅⋅⋅1000000000039
14桁⋅⋅⋅10000000000037
15桁⋅⋅⋅100000000000031
16桁⋅⋅⋅1000000000000037
17桁⋅⋅⋅10000000000000061
18桁⋅⋅⋅100000000000000003
19桁⋅⋅⋅1000000000000000003
20桁⋅⋅⋅10000000000000000051

・強連結成分分解
def scc(N,edges):
    M=len(edges)
    start=[0]*(N+1)
    elist=[0]*M
    for e in edges:
        start[e[0]+1]+=1
    for i in range(1,N+1):
        start[i]+=start[i-1]
    counter=start[:]
    for e in edges:
        elist[counter[e[0]]]=e[1]
        counter[e[0]]+=1
    visited=[]
    low=[0]*N
    Ord=[-1]*N
    ids=[0]*N
    NG=[0,0]
    def dfs(v):
        stack=[(v,-1,0),(v,-1,1)]
        while stack:
            v,bef,t=stack.pop()
            if t:
                if bef!=-1 and Ord[v]!=-1:
                    low[bef]=min(low[bef],Ord[v])
                    stack.pop()
                    continue
                low[v]=NG[0]
                Ord[v]=NG[0]
                NG[0]+=1
                visited.append(v)
                for i in range(start[v],start[v+1]):
                    to=elist[i]
                    if Ord[to]==-1:
                        stack.append((to,v,0))
                        stack.append((to,v,1))
                    else:
                        low[v]=min(low[v],Ord[to])
            else:
                if low[v]==Ord[v]:
                    while(True):
                        u=visited.pop()
                        Ord[u]=N
                        ids[u]=NG[1]
                        if u==v:
                            break
                    NG[1]+=1
                low[bef]=min(low[bef],low[v])
    for i in range(N):
        if Ord[i]==-1:
            dfs(i)
    for i in range(N):
        ids[i]=NG[1]-1-ids[i]
    group_num=NG[1]
    counts=[0]*group_num
    for x in ids:
        counts[x]+=1
    groups=[[] for i in range(group_num)]
    for i in range(N):
        groups[ids[i]].append(i)
    return groups

・拡張ユークリッドの互除法
def extended_euclid(a, b):
    if b == 0:
        return (1, 0)
    else:
        xd, yd = extended_euclid(b, a % b)
        return (yd, xd - a // b * yd)

・重み付きUnionFind
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.weight = [0] * n

    def leader(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.leader(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def merge(self, x, y, w):
        rx = self.leader(x)
        ry = self.leader(y)
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[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.leader(x) == self.leader(y)

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

・3点が同一線上にあるか
def judge(x1, y1, x2, y2, x3, y3):
    return (x1-x3)*(y2-y3)-(x2-x3)*(y1-y3) == 0

・全方位木dp
def LRset(n):
    for i in range(1, len(G[n])):
        L[n][i] = L[n][i-1]+dp[n][i-1]
    for i in reversed(range(len(G[n])-1)):
        R[n][i] = R[n][i+1]+dp[n][i+1]

L = [[0]*len(G[i]) for i in range(N)]
R = [[0]*len(G[i]) for i in range(N)]
LRset(0)

@bootstrap
def rerooting(n, pre, no):
    visited[n] = True
    preno = 0
    for i in range(len(G[n])):
        if G[n][i] == pre:
            preno = i
            break
    dp[n][preno] = L[pre][no]+R[pre][no]+1
    LRset(n)
    for i in range(len(G[n])):
        if not visited[G[n][i]]:
            yield rerooting(G[n][i], n, i)
    yield

visited = [False]*N
visited[0] = True
for i in range(len(G[0])):
    if not visited[G[0][i]]:
        rerooting(G[0][i], 0, i)

・Z-algorithm
def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

・ローリングハッシュ
class RollingHash:
    def __init__(self, S, type):
        if type == False:
            a = ord("a")-1
        else:
            a = ord("A")-1
        self.hash = [0]
        for i in range(len(S)):
            self.hash.append((self.hash[-1]*26+(ord(S[i])-a))%MOD)
        self.POW = [1]
        for i in range(len(S)):
            self.POW.append(self.POW[-1]*26%MOD)
    
    def query(self, l, r):
        return (self.hash[r]-self.hash[l]*self.POW[r-l])%MOD

・最小共通祖先
class LCA:
    def __init__(self, G, root=0):
        V = len(G)
        self.bit_length = 1
        while 1<<self.bit_length < V:
            self.bit_length += 1
        self.parent = [[-1]*V for _ in range(self.bit_length)]
        self.depth = [-1]*V
        self.bfs(G, root)
        for i in range(self.bit_length-1):
            for j in range(V):
                if self.parent[i][j] != -1:
                    self.parent[i+1][j] = self.parent[i][self.parent[i][j]]
        
    def bfs(self, G, root):
        self.depth[root] = 0
        que = deque()
        que.append(root)
        while que:
            n = que.popleft()
            for v in G[n]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[n]+1
                    self.parent[0][v] = n
                    que.append(v)
    
    def lca(self, a, b):
        if self.depth[a] < self.depth[b]:
            a, b = b, a
        for i in range(self.bit_length):
            if (self.depth[a]-self.depth[b]) & 1<<i:
                a = self.parent[i][a]
        if a == b:
            return a
        for i in reversed(range(self.bit_length)):
            if self.parent[i][a] != self.parent[i][b]:
                a = self.parent[i][a]
                b = self.parent[i][b]
        return self.parent[0][a]
    
    def dist(self, a, b):
        return self.depth[a]+self.depth[b]-self.depth[self.lca(a, b)]*2
    
    def is_ancestor(self, u, v):
        return self.lca(u, v) == u
    
    def kth_ancestor(self, n, k):
        for i in range(self.bit_length):
            if 1<<i & k:
                n = self.parent[i][n]
                if n == -1:
                    break
        return n
    
    def jump(self, u, v):
        if u == v:
            return u
        if self.lca(u, v) == u:
            return self.kth_ancestor(v, self.dist(u, v)-1)
        else:
            return self.parent[0][u]
    
    def jump_k(self, u, v, k):
        d = self.dist(u, v)
        if d <= k:
            return v
        lca = self.lca(u, v)
        if k <= self.depth[u]-self.depth[lca]:
            return self.kth_ancestor(u, k)
        else:
            return self.kth_ancestor(v, d-k)
    
    def on_path(self, u, v, x):
        return self.dist(u, x)+self.dist(x, v) == self.dist(u, v)

    def create_path(self, u, v, x):
        if self.on_path(u, v, x):
            return u, v
        if self.on_path(u, x, v):
            return u, x
        if self.on_path(v, x, u):
            return v, x
        return -1, -1

・HL分解（辺）
class HLDecomposition:
    def __init__(self, N, G, segfunc, ide_ele):
        self.N = N
        self.G = G
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.parent = [-1]*N
        self.depth = [0]*N
        self.size = [1]*N
        self.heavy = [-1]*N

        self.visited = [False]*N
        self.build1(0)

        self.top = [0]*N
        self.HLD_G = [0]
        self.visited = [False]*N
        self.build2(0)
        self.HLD_G = self.HLD_G[::-1]

        self.node_w = [0]*N
        self.node = [N-1]*N
        self.make_tree()
    
    def update(self, v, w, weight):
        if self.parent[w] == v:
            v, w = w, v
        elif self.parent[v] != w:
            return False
        self.Tree.update(self.node[v], weight)
    
    def query(self, l, r):
        sml, smr = self.ide_ele, self.ide_ele
        while True:
            li, ri = self.node[l], self.node[r]
            if self.top[l] == self.top[r]:
                if self.depth[l] > self.depth[r]:
                    sml = self.segfunc(sml, self.Tree.query(li, ri))
                else:
                    smr = self.segfunc(self.Tree.query(ri, li), smr)
                return self.segfunc(sml, smr)
            else:
                l_top, r_top = self.top[l], self.top[r]
                if self.depth[l_top] > self.depth[r_top]:
                    sml = self.segfunc(sml, self.Tree.query(li, self.node[l_top]+1))
                    l = self.parent[l_top]
                else:
                    smr = self.segfunc(self.Tree.query(ri, self.node[r_top]+1), smr)
                    r = self.parent[r_top]
    
    @bootstrap
    def build1(self, n):
        self.visited[n] = True
        for v, _ in self.G[n]:
            if not self.visited[v]:
                self.parent[v] = n
                self.depth[v] = self.depth[n]+1
                self.size[n] += yield self.build1(v)
                if self.heavy[n] == -1 or self.size[self.heavy[n]] < self.size[v]:
                    self.heavy[n] = v
        yield self.size[n]
    
    @bootstrap
    def build2(self, n):
        self.visited[n] = True
        if self.heavy[n] != -1:
            v = self.heavy[n]
            self.top[v] = self.top[n]
            self.HLD_G.append(v)
            yield self.build2(v)
        for v, _ in self.G[n]:
            if not self.visited[v] and v != self.heavy[n]:
                self.top[v] = v
                self.HLD_G.append(v)
                yield self.build2(v)
        yield
    
    def make_tree(self):
        for i, n in enumerate(self.HLD_G[:-1]):
            for v, w in self.G[n]:
                if v == self.parent[n]:
                    self.node_w[i] = w
                    break
            self.node[n] = i
        self.Tree = SegTree(self.node_w, self.segfunc, self.ide_ele)

・HL分解（頂点）
class HLDecomposition:
    def __init__(self, N, G, segfunc, ide_ele):
        self.N = N
        self.G = G
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.parent = [-1]*N
        self.depth = [0]*N
        self.size = [1]*N
        self.heavy = [-1]*N

        self.visited = [False]*N
        self.build1(0)

        self.top = [0]*N
        self.HLD_G = [0]
        self.visited = [False]*N
        self.build2(0)
        self.HLD_G = self.HLD_G[::-1]

        self.node_w = [0]*N
        self.node = [N-1]*N
        self.make_tree()
    
    def update(self, n, weight):
        self.Tree.update(self.node[n], weight)
    
    def query(self, l, r):
        sml, smr = self.ide_ele, self.ide_ele
        while True:
            li, ri = self.node[l], self.node[r]
            if self.top[l] == self.top[r]:
                if self.depth[l] > self.depth[r]:
                    sml = self.segfunc(sml, self.Tree.query(li, ri+1))
                else:
                    smr = self.segfunc(self.Tree.query(ri, li+1), smr)
                return self.segfunc(sml, smr)
            else:
                l_top, r_top = self.top[l], self.top[r]
                if self.depth[l_top] > self.depth[r_top]:
                    sml = self.segfunc(sml, self.Tree.query(li, self.node[l_top]+1))
                    l = self.parent[l_top]
                else:
                    smr = self.segfunc(self.Tree.query(ri, self.node[r_top]+1), smr)
                    r = self.parent[r_top]
    
    @bootstrap
    def build1(self, n):
        self.visited[n] = True
        for v in self.G[n]:
            if not self.visited[v]:
                self.parent[v] = n
                self.depth[v] = self.depth[n]+1
                self.size[n] += yield self.build1(v)
                if self.heavy[n] == -1 or self.size[self.heavy[n]] < self.size[v]:
                    self.heavy[n] = v
        yield self.size[n]
    
    @bootstrap
    def build2(self, n):
        self.visited[n] = True
        if self.heavy[n] != -1:
            v = self.heavy[n]
            self.top[v] = self.top[n]
            self.HLD_G.append(v)
            yield self.build2(v)
        for v in self.G[n]:
            if not self.visited[v] and v != self.heavy[n]:
                self.top[v] = v
                self.HLD_G.append(v)
                yield self.build2(v)
        yield
    
    def make_tree(self):
        for i, n in enumerate(self.HLD_G):
            self.node_w[i] = A[n]
            self.node[n] = i
        self.Tree = SegTree(self.node_w, self.segfunc, self.ide_ele)

・等比数列
def geometric_progression(a, r, n):
    # a = 初項 r = 公比 n = 項数
    return a*((pow(r, n, MOD)-1)%MOD)%MOD*inverse(1, r-1)%MOD

・ベクトル
def vec(a, b):
    return (b[0]-a[0], b[1]-a[1])

・ベクトルの絶対値
def vec2(a):
    return (a[0]**2+a[1]**2)**0.5

・内積
def inner_product(v1, v2):
    return v1[0]*v2[0]+v1[1]*v2[1]

・外積
def cross_product(v1, v2):
    return v1[0]*v2[1]-v1[1]*v2[0]

・∠BACの角度
def angle(bx, by, ax, ay, cx, cy):
    ab = vec((ax, ay), (bx, by))
    ac = vec((ax, ay), (cx, cy))
    top = ab[0]*ac[0]+ab[1]*ac[1]
    if cross_product(ab, ac) <= 0:
        return degrees(acos(top/(vec2(ab)*vec2(ac))))
    else:
        return 360-degrees(acos(top/(vec2(ab)*vec2(ac))))

・組み合わせの数
class CP:
    def __init__(self, N):
        self.fact = [1]*(N+1)
        self.fact_inv = [1]*(N+1)
        for i in range(2, N+1):
            self.fact[i] = self.fact[i-1]*i%MOD
        self.fact_inv[N] = pow(self.fact[N], -1, MOD)
        for i in reversed(range(1, N)):
            self.fact_inv[i] = self.fact_inv[i+1]*(i+1)%MOD
    def C(self, N, K):
        if N < 0 or K < 0 or N < K:
            return 0
        return self.fact[N]*self.fact_inv[K]%MOD*self.fact_inv[N-K]%MOD
    def P(self, N, K):
        if N < 0 or K < 0 or N < K:
            return 0
        return self.fact[N]*self.fact_inv[N-K]%MOD
    def H(self, N, K):
        if N < 0 or K < 0:
            return 0
        if N == K == 0: return 1
        return self.C(N+K-1, K)

・Dinic
class Dinic_edge:
    def __init__(self, t, cap, rev):
        self.t = t
        self.cap = cap
        self.rev = rev

class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for _ in range(N)]
    
    def add_edge(self, u, v, cap):
        self.G[u].append(Dinic_edge(v, cap, len(self.G[v])))
        self.G[v].append(Dinic_edge(u, 0, len(self.G[u])-1))
    
    def bfs(self, s, to):
        self.level = [-1]*self.N
        que = deque()
        que.append(s)
        self.level[s] = 0
        while que:
            n = que.popleft()
            for v in self.G[n]:
                if v.cap and self.level[v.t] == -1:
                    self.level[v.t] = self.level[n]+1
                    que.append(v.t)
        return self.level[to] != -1

    @bootstrap
    def dfs(self, n, to, f):
        if n == to:
            yield f
        for v in self.it[n]:
            if v.cap and self.level[n] < self.level[v.t]:
                d = yield self.dfs(v.t, to, min(f, v.cap))
                if d:
                    v.cap -= d
                    self.G[v.t][v.rev].cap += d
                    yield d
        yield 0
    
    def flow(self, s, t):
        flow = 0
        INF = 10**18
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

・ポラード・ロー素因数分解
def gcd(a, b):
    while a:
        a, b = b%a, a
    return b

def is_prime(n):
    if n == 2:
        return 1
    if n == 1 or n%2 == 0:
        return 0

    m = n - 1
    lsb = m & -m
    s = lsb.bit_length()-1
    d = m // lsb

    test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

    for a in test_numbers:
        if a == n:
            continue
        x = pow(a,d,n)
        r = 0
        if x == 1:
            continue
        while x != m:
            x = pow(x,2,n)
            r += 1
            if x == 1 or r == s:
                return 0
    return 1

def find_prime_factor(n):
    if n%2 == 0:
        return 2

    m = int(n**0.125)+1

    for c in range(1,n):
        f = lambda a: (pow(a,2,n)+c)%n
        y = 0
        g = q = r = 1
        k = 0
        while g == 1:
            x = y
            while k < 3*r//4:
                y = f(y)
                k += 1
            while k < r and g == 1:
                ys = y
                for _ in range(min(m, r-k)):
                    y = f(y)
                    q = q*abs(x-y)%n
                g = gcd(q,n)
                k += m
            k = r
            r *= 2
        if g == n:
            g = 1
            y = ys
            while g == 1:
                y = f(y)
                g = gcd(abs(x-y),n)
        if g == n:
            continue
        if is_prime(g):
            return g
        elif is_prime(n//g):
            return n//g
        else:
            return find_prime_factor(g)

def factorize(n):
    res = []
    while not is_prime(n) and n > 1:  # nが合成数である間nの素因数の探索を繰り返す
        p = find_prime_factor(n)
        s = 0
        while n%p == 0:  # nが素因数pで割れる間割り続け、出力に追加
            n //= p
            s += 1
        res.append((p, s))
    if n > 1:  # n>1であればnは素数なので出力に追加
        res.append((n, 1))
    return res

def divisor(n):
    ans = [1]
    pf = factorize(n)
    for p, c in pf:
        L = len(ans)
        for i in range(L):
            v = 1
            for _ in range(c):
                v *= p
                ans.append(ans[i]*v)
    return sorted(ans)

・行列の積
def matrix(a, b):
    ans = [[0]*len(b[0]) for _ in range(len(a))]
    for i in range(len(a)):
        for j in range(len(b[0])):
            for k in range(len(b)):
                ans[i][j] += a[i][k]*b[k][j]%MOD
                ans[i][j] %= MOD
    return ans

・座標と行列から移動後の座標を求める
def place(a, b):
    X = sum(a[0][i]*b[i] for i in range(3))
    Y = sum(a[1][i]*b[i] for i in range(3))
    return X, Y

・変換行列
def OP(n, p):
    # 時計回りに90度回転
    if n == 1:
        A = [(0, 1, 0), (-1, 0, 0), (0, 0, 1)]
    # 反時計回りに90度回転
    elif n == 2:
        A = [(0, -1, 0), (1, 0, 0), (0, 0, 1)]
    # x軸pに対称な位置に移動
    elif n == 3:
        A = [(-1, 0, 2*p), (0, 1, 0), (0, 0, 1)]
    # y軸pに対称な位置に移動
    else:
        A = [(1, 0, 0), (0, -1, 2*p), (0, 0, 1)]
    return A

・WaveletMatrix
from itertools import accumulate
from typing import Optional

class BitVector:
    def __init__(self, B: list[int]):
        self.B = B
        self.acc = list(accumulate(B))

    def __len__(self) -> int:
        return len(self.B)

    def __getitem__(self, i: int) -> int:
        return self.B[i]

    def rank0(self, i: int) -> int:
        if i <= 0:
            return 0
        i = min(i, len(self))
        return i - self.rank1(i)

    def rank1(self, i: int) -> int:
        if i <= 0:
            return 0
        i = min(i, len(self))
        return self.acc[i - 1]

    def rank0_all(self) -> int:
        return self.rank0(len(self.B))

    def rank1_all(self) -> int:
        return self.rank1(len(self.B))

    def select0(self, k: int) -> Optional[int]:
        if (k <= 0) or (k > self.rank0_all()):
            return None

        left, right = 0, len(self)
        while (right - left) > 1:
            mid = (left + right) // 2
            if self.rank0(mid) < k:
                left = mid
            else:
                right = mid
        return left

    def select1(self, k: int) -> Optional[int]:
        if (k <= 0) or (k > self.rank1_all()):
            return None

        left, right = 0, len(self)
        while (right - left) > 1:
            mid = (left + right) // 2
            if self.rank1(mid) < k:
                left = mid
            else:
                right = mid
        return left

class WaveletMatrix:
    def __init__(self, T: list[int]):
        self.bit_size: int = max(T).bit_length() if T else 0
        self.wavelet_matrix: list[BitVector] = self._build(T)

    def _build(self, T: list[int]) -> list[BitVector]:
        wavelet_matrix: list[BitVector] = []
        for digit in range(self.bit_size)[::-1]:
            zeros = [t for t in T if not self._get_i_bit(t, digit + 1)]
            ones = [t for t in T if self._get_i_bit(t, digit + 1)]

            T = zeros + ones
            wavelet_matrix.append(BitVector([self._get_i_bit(t, digit) for t in T]))
        return wavelet_matrix

    def __len__(self) -> int:
        if len(self.wavelet_matrix) == 0:
            return 0
        return len(self.wavelet_matrix[0])

    def __getitem__(self, i: int) -> int:
        return self.access(i)

    def _get_i_bit(self, x: int, digit: int) -> int:
        return 1 & (x >> digit)

    def _next_range(self, B: BitVector, bit: int, left: int, right: int) -> tuple[int, int]:
        if bit == 0:
            left = B.rank0(left)
            right = B.rank0(right)
        else:
            left = B.rank0_all() + B.rank1(left)
            right = B.rank0_all() + B.rank1(right)
        return (left, right)

    def access(self, i: int) -> int:
        x = 0
        for digit, B in enumerate(self.wavelet_matrix):
            bit = B[i]
            x |= bit << (self.bit_size - digit - 1)

            if bit == 0:
                i = B.rank0(i + 1) - 1
            else:
                i = B.rank0_all() + B.rank1(i + 1) - 1
        return x

    # T[0..right)におけるxの出現回数
    def rank(self, x: int, right: int) -> int:
        return self.rank_range(x, 0, right)

    # T[left..right)におけるxの出現回数
    def rank_range(self, x: int, left: int, right: int) -> int:
        if (left >= right) or (x.bit_length() > self.bit_size) or (x < 0):
            return 0

        left = max(left, 0)
        right = min(right, len(self))
        for digit, B in enumerate(self.wavelet_matrix):
            x_bit = self._get_i_bit(x, self.bit_size - digit - 1)
            left, right = self._next_range(B, x_bit, left, right)
        return right - left

    # 元の配列Tのk個目のxの出現位置 (index)
    def select(self, x: int, k: int) -> Optional[int]:
        if not (0 <= x < 1 << self.bit_size):
            return None
        if k <= 0:
            return None

        # xが最終的な配列のどの範囲に入るか計算
        left, right = 0, len(self)
        for digit, B in enumerate(self.wavelet_matrix):
            x_bit = self._get_i_bit(x, self.bit_size - digit - 1)
            left, right = self._next_range(B, x_bit, left, right)

        if left >= right:
            return None

        # 上記範囲のk番目が, 元の配列で何番目か計算
        index = left + k - 1
        for digit, B in enumerate(self.wavelet_matrix[::-1]):
            if index is None:
                return None

            x_bit = self._get_i_bit(x, digit)
            if x_bit == 0:
                index = B.select0(index + 1)
            else:
                index = B.select1(index - (B.rank0_all() - 1))
        return index

    # 元の配列T[left..right)の中のk番目に小さい値
    def quantile(self, left: int, right: int, k: int) -> Optional[int]:
        if (left >= right) or (k <= 0) or (right - left < k):
            return None

        left = max(left, 0)
        right = min(right, len(self))

        x = 0
        for digit, B in enumerate(self.wavelet_matrix):
            num_zeros = B.rank0(right) - B.rank0(left)

            # 該当要素が0の中か or 1の中か
            bit = 0 if k <= num_zeros else 1
            left, right = self._next_range(B, bit, left, right)

            if bit == 1:
                k -= num_zeros
                x |= bit << (self.bit_size - digit - 1)
        return x

    # T[left..right)の0 <= x < upper となるxの個数
    def range_freq_to(self, left: int, right: int, upper: int) -> int:
        if (left >= right) or (upper <= 0):
            return 0

        # 全ての要素が < upper
        if upper.bit_length() > self.bit_size:
            return right - left

        cnt = 0
        left = max(left, 0)
        right = min(right, len(self))
        for digit, B in enumerate(self.wavelet_matrix):
            upper_bit = self._get_i_bit(upper, self.bit_size - digit - 1)
            if upper_bit == 1:
                cnt += B.rank0(right) - B.rank0(left)

            left, right = self._next_range(B, upper_bit, left, right)

        return cnt

    # T[left..right)のlower <= x となるxの個数
    def range_freq_from(self, left: int, right: int, lower: int) -> int:
        if (left >= right) or (lower > (1 << self.bit_size)):
            return 0

        left = max(left, 0)
        right = min(right, len(self))
        return (right - left) - self.range_freq_to(left, right, lower)

    # T[left..right)のlower <= x < upper となるxの個数
    def range_freq(self, left: int, right: int, lower: int, upper: int) -> int:
        if (left >= right) or (lower >= upper) or (lower > (1 << self.bit_size)):
            return 0

        return self.range_freq_to(left, right, upper) - self.range_freq_to(
            left, right, lower
        )

    # T[left..right)の中で0 <= x < upperを満たす最大のx
    def prev_value(self, left: int, right: int, upper: int) -> Optional[int]:
        cnt = self.range_freq_to(left, right, upper)
        if cnt == 0:
            return None
        return self.quantile(left, right, cnt)

    # T[left..right)の中で, lower <= x を満たす最小のx
    def next_value(self, left: int, right: int, lower: int) -> int:
        cnt = self.range_freq_from(left, right, lower)
        if cnt == 0:
            return None
        return self.quantile(left, right, right - left - cnt + 1)

・HopcroftKarp
import sys
sys.setrecursionlimit(10**6)

class HopcroftKarp:
    def __init__(self, N1, N2):
        self.N1 = N1
        self.N2 = N2
        self.G = [[] for _ in range(self.N1+1)]
        self.pair1 = [0]*(self.N1+1)
        self.pair2 = [0]*(self.N2+1)
        self.matching_size = -1
        
    def add_edge(self, fr, to):
        self.G[fr].append(to)
    
    def bfs(self):
        que = deque()
        for i in range(1, self.N1+1):
            if self.pair1[i] == 0:
                self.dist[i] = 0
                que.append(i)
            else:
                self.dist[i] = INF
        self.dist[0] = INF
        while que:
            n = que.popleft()
            if self.dist[n] < self.dist[0]:
                for v in self.G[n]:
                    if self.dist[self.pair2[v]] == INF:
                        self.dist[self.pair2[v]] = self.dist[n]+1
                        que.append(self.pair2[v])
        return self.dist[0] != INF

    def dfs(self, n):
        if n != 0:
            for v in self.G[n]:
                if self.dist[self.pair2[v]] == self.dist[n]+1:
                    if self.dfs(self.pair2[v]):
                        self.pair2[v] = n
                        self.pair1[n] = v
                        return True
            self.dist[n] = INF
            return False
        return True
    
    def flow(self):
        if self.matching_size != -1:
            return self.matching_size
        self.dist = [0]*(self.N1+1)
        ans = 0
        while self.bfs():
            for i in range(1, self.N1+1):
                if self.pair1[i] == 0 and self.dfs(i):
                    ans += 1
        self.matching_size = ans
        return ans
    
    def get_matching(self):
        if self.matching_size == -1:
            self.flow()
        ans = []
        for i in range(1, self.N1+1):
            if self.pair1[i] != 0:
                ans.append((i, self.pair1[i]))
        return ans
    
    def minimum_vertex_cover(self):
        if self.matching_size == -1:
            self.flow()
        return self.matching_size
    
    def maximum_independent_set(self):
        return self.N1+self.N2-self.minimum_vertex_cover()
    
    def minimum_edge_cover(self):
        F = [False]*(self.N1+self.N2+1)
        for n in range(1, self.N1+1):
            F[n] = True
            for v in self.G[n]:
                F[self.N1+v] = True
        if sum(F) < self.N1+self.N2:
            return -1
        if self.matching_size == -1:
            self.flow()
        return self.N1+self.N2-self.matching_size
    
    def preparation(self):
        if self.matching_size == -1:
            self.flow()
        L = self.N1+self.N2
        G = [[] for _ in range(L+1)]
        for n in range(1, self.N1+1):
            for v in self.G[n]:
                if self.pair1[n] == v:
                    G[self.N1+v].append(n)
                else:
                    G[n].append(self.N1+v)

        visited = [False]*(L+1)
        que = deque()
        for i in range(1, self.N1+1):
            if self.pair1[i] == 0:
                visited[i] = True
                que.append(i)
        while que:
            n = que.popleft()
            for v in G[n]:
                if not visited[v]:
                    visited[v] = True
                    que.append(v)
        return visited

    def get_minimum_vertex_cover(self):
        visited = self.preparation()
        ans1 = []
        ans2 = []
        for i in range(1, self.N1+self.N2+1):
            if i <= self.N1 and not visited[i]:
                ans1.append(i)
            elif self.N1+1 <= i and visited[i]:
                ans2.append(i-self.N1)
        return ans1, ans2
    
    def get_maximum_independent_set(self):
        visited = self.preparation()
        ans1 = []
        ans2 = []
        for i in range(1, self.N1+self.N2+1):
            if i <= self.N1 and visited[i]:
                ans1.append(i)
            elif self.N1+1 <= i and not visited[i]:
                ans2.append(i-self.N1)
        return ans1, ans2
    
    def get_minimum_edge_cover(self):
        cnt = self.minimum_edge_cover()
        if cnt == -1:
            return None
        ans = []
        pair = [-1]*(self.N1+self.N2+1)
        for n in range(1, self.N1+1):
            pair[n] = self.G[n][0]
            for v in self.G[n]:
                if pair[self.N1+v] == -1:
                    pair[self.N1+v] = n
        for i in range(1, self.N1+self.N2+1):
            if i <= self.N1 and self.pair1[i] != 0:
                ans.append((i, self.pair1[i]))
            elif i <= self.N1 and self.pair1[i] == 0:
                ans.append((i, pair[i]))
            elif self.N1+1 <= i and self.pair2[i-self.N1] == 0:
                ans.append((pair[i], i-self.N1))
        return ans

・Suffix Array(SA-IS)
from collections import Counter

# SA-IS (O(nlogn))
# s: 文字列
def sais(s):
    uniq = list(set(s))
    uniq.sort()
    return sais_rec(list(map({e: i+1 for i, e in enumerate(uniq)}.__getitem__, s)), len(uniq))
def sais_rec(lst, num):
    L = len(lst)
    if L < 2:
        return lst + [0]
    lst = lst + [0]
    L += 1
    res = [-1] * L
    t = [1] * L
    for i in range(L-2, -1, -1):
        t[i] = 1 if (lst[i] < lst[i+1] or (lst[i] == lst[i+1] and t[i+1])) else 0
    isLMS = [t[i-1] < t[i] for i in range(L)]
    LMS = [i for i in range(1, L) if t[i-1] < t[i]]
    LMSn = len(LMS)

    count = Counter(lst)
    tmp = 0
    cstart = [0]*(num+1)
    cend = [0]*(num+1)
    for key in range(num+1):
        cstart[key] = tmp
        cend[key] = tmp = tmp + count[key]

    cc_it = [iter(range(e-1, s-1, -1)) for s, e in zip(cstart, cend)]
    for e in reversed(LMS):
        res[next(cc_it[lst[e]])] = e

    cs_it = [iter(range(s, e)) for s, e in zip(cstart, cend)]
    ce_it = [iter(range(e-1, s-1, -1)) for s, e in zip(cstart, cend)]
    for e in res:
        if e > 0 and not t[e-1]:
            res[next(cs_it[lst[e-1]])] = e-1
    for e in reversed(res):
        if e > 0 and t[e-1]:
            res[next(ce_it[lst[e-1]])] = e-1

    name = 0; prev = -1
    pLMS = {}
    for e in res:
        if isLMS[e]:
            if prev == -1 or lst[e] != lst[prev]:
                name += 1; prev = e
            else:
                for i in range(1, L):
                    if lst[e+i] != lst[prev+i]:
                        name += 1; prev = e
                        break
                    if isLMS[e+i] or isLMS[prev+i]:
                        break
            pLMS[e] = name-1

    if name < LMSn:
        sublst = [pLMS[e] for e in LMS if e < L-1]
        ret = sais_rec(sublst, name-1)

        LMS = list(map(LMS.__getitem__, reversed(ret)))
    else:
        LMS = [e for e in reversed(res) if isLMS[e]]

    res = [-1] * L

    cc_it = [iter(range(e-1, s-1, -1)) for s, e in zip(cstart, cend)]
    for e in LMS:
        res[next(cc_it[lst[e]])] = e

    cs_it = [iter(range(s, e)) for s, e in zip(cstart, cend)]
    ce_it = [iter(range(e-1, s-1, -1)) for s, e in zip(cstart, cend)]

    for e in res:
        if e > 0 and not t[e-1]:
            res[next(cs_it[lst[e-1]])] = e-1
    for e in reversed(res):
        if e > 0 and t[e-1]:
            res[next(ce_it[lst[e-1]])] = e-1
    return res

# Longest Common Prefix
# (文字列s, 文字列長n, Suffix Array)を引数として与える
def LCP(s, n, sa):
    lcp = [-1]*(n+1)
    rank = [0]*(n+1)
    for i in range(n+1): rank[sa[i]] = i

    h = 0
    lcp[0] = 0
    for i in range(n):
        j = sa[rank[i] - 1]
        if h > 0: h -= 1
        while j+h < n and i+h < n and s[j+h]==s[i+h]:
            h += 1
        lcp[rank[i] - 1] = h
    return lcp

・最小費用流
# https://atcoder.jp/contests/practice2/submissions/33588016
from heapq import heappush, heappop

class MinCostFlow:
    """
    https://github.com/atcoder/ac-library/blob/master/atcoder/internal_csr.hpp
    https://github.com/atcoder/ac-library/blob/master/atcoder/mincostflow.hpp
    https://github.com/atcoder/ac-library/blob/master/document_en/mincostflow.md
    https://github.com/atcoder/ac-library/blob/master/document_ja/mincostflow.md
    """
    def __init__(self, n):
        self.n = n
        self._edges = []

    def add_edge(self, fr, to, cap, cost):
        assert 0 <= fr < self.n
        assert 0 <= to < self.n
        assert 0 <= cap
        assert 0 <= cost
        self._edges.append(self.edge(fr, to, cap, cost))
        return len(self._edges) - 1

    class edge:
        def __init__(self, fr, to, cap, cost):
            self.fr = fr
            self.to = to
            self.cap = cap
            self.flow = 0
            self.cost = cost

    def get_edge(self, i):
        assert 0 <= i < len(self._edges)
        return self._edges[i]

    def edges(self):
        return self._edges

    def flow(self, s, t, flow_limit=1<<60):
        return self.slope(s, t, flow_limit)[-1]

    def __csr(self, edges):
        # Compressed Sparse Row
        self.start = [0] * (self.n + 1)
        for fr, _ in edges:
            self.start[fr + 1] += 1
        for i in range(self.n):
            self.start[i + 1] += self.start[i]
        counter = self.start.copy()
        self.elist = [0] * len(edges)
        for fr, e in edges:
            self.elist[counter[fr]] = e
            counter[fr] += 1

    class _edge:
        def __init__(self, to, rev, cap, cost):
            self.to = to
            self.rev = rev
            self.cap = cap
            self.cost = cost

    def __g(self):
        degree = [0] * self.n
        redge_idx = [0] * self.m
        elist = [(0, None)] * (2 * self.m)
        now_elist = 0
        for i in range(self.m):
            e = self._edges[i]
            self.edge_idx[i] = degree[e.fr]
            degree[e.fr] += 1
            redge_idx[i] = degree[e.to]
            degree[e.to] += 1
            elist[now_elist] = (e.fr, self._edge(e.to, -1, e.cap - e.flow, e.cost))
            now_elist += 1
            elist[now_elist] = (e.to, self._edge(e.fr, -1, e.flow, -e.cost))
            now_elist += 1
        self.__csr(elist)
        for i in range(self.m):
            e = self._edges[i]
            self.edge_idx[i] += self.start[e.fr]
            redge_idx[i] += self.start[e.to]
            self.elist[self.edge_idx[i]].rev = redge_idx[i]
            self.elist[redge_idx[i]].rev = self.edge_idx[i]

    def slope(self, s, t, flow_limit=1<<60):
        assert 0 <= s < self.n
        assert 0 <= t < self.n
        assert s != t
        self.m = len(self._edges)
        self.edge_idx = [0] * self.m
        self.__g()
        result = self.__slope(s, t, flow_limit)
        for i in range(self.m):
            e = self.elist[self.edge_idx[i]]
            self._edges[i].flow = self._edges[i].cap - e.cap
        return result

    def __dual_ref(self, s, t):
        log = self.n.bit_length()
        mask = (1<<log) - 1
        dist = [1<<60] * self.n
        vis = [0] * self.n
        que_min = []
        que = []
        dist[s] = 0
        que_min.append(s)
        while que_min or que:
            if que_min:
                v = que_min.pop()
            else:
                v = heappop(que) & mask
            if vis[v]:
                continue
            vis[v] = 1
            if v == t:
                break
            # dist[v] = shortest(s, v) + dual[s] - dual[v]
            # dist[v] >= 0 (all reduced cost are positive)
            # dist[v] <= (n-1)C
            dual_v = self.dual[v]
            dist_v = dist[v]
            for i in range(self.start[v], self.start[v+1]):
                e = self.elist[i]
                if not e.cap:
                    continue
                # |-dual[e.to] + dual[v]| <= (n-1)C
                # cost <= C - -(n-1)C + 0 = nC
                cost = e.cost - self.dual[e.to] + dual_v
                if dist[e.to] - dist_v > cost:
                    dist_to = dist_v + cost
                    dist[e.to] = dist_to
                    self.prev_e[e.to] = e.rev
                    if dist_to == dist_v:
                        que_min.append(e.to)
                    else:
                        heappush(que, dist_to<<log | e.to)
        if not vis[t]:
            return False
        for v in range(self.n):
            if not vis[v]:
                continue
            # dual[v]
            # = dual[v] - dist[t] + dist[v]
            # = dual[v] - (shortest(s, t) + dual[s] - dual[t]) + (shortest(s, v) + dual[s] - dual[v])
            # = - shortest(s, t) + dual[t] + shortest(s, v)
            # = shortest(s, v) - shortest(s, t)
            # >= 0 - (n-1)C
            self.dual[v] -= dist[t] - dist[v]
        return True

    def __slope(self, s, t, flow_limit):
        # variants (C = maxcost):
        # -(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0
        # reduced cost (= e.cost + dual[e.from] - dual[e.to]) >= 0 for all edge
        self.dual = [0] * self.n
        self.prev_e = [0] * self.n
        flow = 0
        cost = 0
        prev_cost_per_flow = -1
        result = [(0, 0)]
        while flow < flow_limit:
            if not self.__dual_ref(s, t):
                break
            c = flow_limit - flow
            v = t
            while v != s:
                c = min(c, self.elist[self.elist[self.prev_e[v]].rev].cap)
                v = self.elist[self.prev_e[v]].to
            v = t
            while v != s:
                e = self.elist[self.prev_e[v]]
                e.cap += c
                self.elist[e.rev].cap -= c
                v = self.elist[self.prev_e[v]].to
            d = -self.dual[s]
            flow += c
            cost += c * d
            if prev_cost_per_flow == d:
                result.pop()
            result.append((flow, cost))
            prev_cost_per_flow = d
        return result

・エラトステネスのふるいを用いた高速素因数分解と高速約数列挙
class Eratosthenes:
    def __init__(self, n):
        self.isPrime = [True]*(n+1)
        self.minfactor = [-1]*(n+1)
        self.isPrime[0], self.isPrime[1] = False, False
        self.minfactor[1] = 1
        for i in range(2, n+1):
            if self.isPrime[i]:
                self.minfactor[i] = i
                for j in range(i*i, n+1, i):
                    self.isPrime[j] = False
                    if self.minfactor[j] == -1:
                        self.minfactor[j] = i
    
    def factorize(self, n):
        factor = []
        while n > 1:
            p = self.minfactor[n]
            cnt = 0
            while self.minfactor[n] == p:
                n //= p
                cnt += 1
            factor.append((p, cnt))
        return factor
    
    def divisor(self, n):
        ans = [1]
        pf = self.factorize(n)
        for p, c in pf:
            L = len(ans)
            for i in range(L):
                v = 1
                for _ in range(c):
                    v *= p
                    ans.append(ans[i]*v)
        return ans

・高速ゼータ変換、高速メビウス変換
def Eratosthenes(n):
    isPrime = [True]*(n+1)
    isPrime[0], isPrime[1] = False, False
    for i in range(2, n+1):
        if isPrime[i]:
            for j in range(i*i, n+1, i):
                isPrime[j] = False
    return isPrime

def fast_zeta(F):
    isPrime = Eratosthenes(len(F))
    print(F)
    for i in range(2, len(F)):
        if isPrime[i]:
            for j in range((len(F)-1)//i, 0, -1):
                F[j] += F[j*i]
            print(F)

def fast_mobius(F):
    isPrime = Eratosthenes(len(F))
    for i in range(2, len(F)):
        if isPrime[i]:
            for j in range(1, (len(F)-1)//i+1):
                F[j] -= F[j*i]

・メビウス関数値の列挙
class Eratosthenes:
    def __init__(self, n):
        self.isPrime = [True]*(n+1)
        self.isPrime[0], self.isPrime[1] = False, False
        self.mobius = [1]*(n+1)
        for i in range(2, n+1):
            if self.isPrime[i]:
                self.mobius[i] = -1
                for j in range(i*2, n+1, i):
                    self.isPrime[j] = False
                    if j//i%i == 0:
                        self.mobius[j] = 0
                    else:
                        self.mobius[j] *= -1

・オイラーのφ関数
def Euler(n):
    div = divisor(n)
    ans = 0
    E = Eratosthenes(n)
    for d in div:
        ans += n//d*E.mobius[d]
    return ans

・座標圧縮
def compress(A):
    S = sorted(set(A))
    D = dict()
    for i in range(len(S)):
        D[S[i]] = i
    return D

・マージソートツリー（X以下や以上の個数）
class MergeSortTree:
    def __init__(self, init_val):
        n = len(init_val)
        self.n = n
        self.num = 1<<(n-1).bit_length()
        self.tree = [[] for _ in range(self.num*2)]
        for i in range(n):
            self.tree[self.num+i].append(init_val[i])
        for i in range(self.num-1, 0, -1):
            left, right = 2*i, 2*i+1
            idxL, idxR = 0, 0
            while idxL < len(self.tree[left]) or idxR < len(self.tree[right]):
                if idxL == len(self.tree[left]):
                    self.tree[i].append(self.tree[right][idxR])
                    idxR += 1
                elif idxR == len(self.tree[right]):
                    self.tree[i].append(self.tree[left][idxL])
                    idxL += 1
                else:
                    if self.tree[left][idxL] <= self.tree[right][idxR]:
                        self.tree[i].append(self.tree[left][idxL])
                        idxL += 1
                    else:
                        self.tree[i].append(self.tree[right][idxR])
                        idxR += 1
    
    # bisectのleftとrightを書き換えれば、Xより小さい数 or Xより大きい数 のクエリにも対応可能
    # sum(A[i] <= X for i in range(l, r))
    def query1(self, l, r, X):
        ans = 0
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                ans += bisect_right(self.tree[l], X)
                l += 1
            if r & 1:
                ans += bisect_right(self.tree[r-1], X)
            l >>= 1
            r >>= 1
        return ans
    # sum(A[i] >= X for i in range(l, r))
    def query2(self, l, r, X):
        ans = 0
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                ans += len(self.tree[l])-bisect_left(self.tree[l], X)
                l += 1
            if r & 1:
                ans += len(self.tree[r-1])-bisect_left(self.tree[r-1], X)
            l >>= 1
            r >>= 1
        return ans
    # sum(leftX <= A[i] <= rightX for i in range(l, r))
    def query3(self, l, r, leftX, rightX):
        ans = r-l
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                ans -= bisect_left(self.tree[l], leftX)
                ans -= len(self.tree[l])-bisect_right(self.tree[l], rightX)
                l += 1
            if r & 1:
                ans -= bisect_left(self.tree[r-1], leftX)
                ans -= len(self.tree[r-1])-bisect_right(self.tree[r-1], rightX)
            l >>= 1
            r >>= 1
        return ans

・マージソートツリー（X以下や以上の個数、総和）
class MergeSortTree:
    def __init__(self, init_val):
        n = len(init_val)
        self.n = n
        self.num = 1<<(n-1).bit_length()
        self.tree = [[] for _ in range(self.num*2)]
        self.cum = [[0] for _ in range(self.num*2)]
        for i in range(n):
            self.tree[self.num+i].append(init_val[i])
        for i in range(self.num-1, 0, -1):
            left, right = 2*i, 2*i+1
            idxL, idxR = 0, 0
            while idxL < len(self.tree[left]) or idxR < len(self.tree[right]):
                if idxL == len(self.tree[left]):
                    self.tree[i].append(self.tree[right][idxR])
                    idxR += 1
                elif idxR == len(self.tree[right]):
                    self.tree[i].append(self.tree[left][idxL])
                    idxL += 1
                else:
                    if self.tree[left][idxL] <= self.tree[right][idxR]:
                        self.tree[i].append(self.tree[left][idxL])
                        idxL += 1
                    else:
                        self.tree[i].append(self.tree[right][idxR])
                        idxR += 1
        for i in range(1, self.num*2):
            for j in range(len(self.tree[i])):
                self.cum[i].append(self.cum[i][-1]+self.tree[i][j])
    
    # bisectのleftとrightを書き換えれば、Xより小さい数 or Xより大きい数 のクエリにも対応可能
    # sum(A[i] <= X for i in range(l, r))
    def query1(self, l, r, X):
        ans = 0
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                ans += bisect_right(self.tree[l], X)
                l += 1
            if r & 1:
                ans += bisect_right(self.tree[r-1], X)
            l >>= 1
            r >>= 1
        return ans
    # sum(A[i] >= X for i in range(l, r))
    def query2(self, l, r, X):
        ans = 0
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                ans += len(self.tree[l])-bisect_left(self.tree[l], X)
                l += 1
            if r & 1:
                ans += len(self.tree[r-1])-bisect_left(self.tree[r-1], X)
            l >>= 1
            r >>= 1
        return ans
    # sum(leftX <= A[i] <= rightX for i in range(l, r))
    def query3(self, l, r, leftX, rightX):
        ans = r-l
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                ans -= bisect_left(self.tree[l], leftX)
                ans -= len(self.tree[l])-bisect_right(self.tree[l], rightX)
                l += 1
            if r & 1:
                ans -= bisect_left(self.tree[r-1], leftX)
                ans -= len(self.tree[r-1])-bisect_right(self.tree[r-1], rightX)
            l >>= 1
            r >>= 1
        return ans
    # sum(A[i] for i in range(l, r) if A[i] <= X)
    def query4(self, l, r, X):
        ans = 0
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                b = bisect_right(self.tree[l], X)
                ans += self.cum[l][b]
                l += 1
            if r & 1:
                b = bisect_right(self.tree[r-1], X)
                ans += self.cum[r-1][b]
            l >>= 1
            r >>= 1
        return ans
    # sum(A[i] for i in range(l, r) if A[i] >= X)
    def query5(self, l, r, X):
        ans = 0
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                b = bisect_left(self.tree[l], X)
                ans += self.cum[l][-1]-self.cum[l][b]
                l += 1
            if r & 1:
                b = bisect_left(self.tree[r-1], X)
                ans += self.cum[r-1][-1]-self.cum[r-1][b]
            l >>= 1
            r >>= 1
        return ans
    # sum(A[i] for i in range(l, r) if leftX <= A[i] <= rightX)
    def query6(self, l, r, leftX, rightX):
        ans = 0
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                left = bisect_left(self.tree[l], leftX)
                right = bisect_right(self.tree[l], rightX)
                ans += self.cum[l][right]-self.cum[l][left]
                l += 1
            if r & 1:
                left = bisect_left(self.tree[r-1], leftX)
                right = bisect_right(self.tree[r-1], rightX)
                ans += self.cum[r-1][right]-self.cum[r-1][left]
            l >>= 1
            r >>= 1
        return ans

・行列の積
def matrix(a, b):
    ans = [[0]*len(b[0]) for _ in range(len(a))]
    for i in range(len(a)):
        for j in range(len(b[0])):
            ans[i][j] = sum(a[i][k]*b[k][j] for k in range(len(b)))
    return ans

・中国剰余定理
def CRT(B, M):
    r, m = 0, 1
    for i in range(len(B)):
        d, x, y = extended_euclid(m, M[i])
        if (B[i]-r)%d != 0:
            return 0, -1
        tmp = (B[i]-r)//d*x%(M[i]//d)
        r += m*tmp
        m *= M[i]//d
    return r, m

・BIT
class BIT:
    def __init__(self, A):
        self.size = len(A)
        self.bit = [0]*(len(A)+1)
        for i in range(len(A)):
            self.add(i, A[i])

    def sum(self, i):
        i += 1
        ans = 0
        while i > 0:
            ans += self.bit[i]
            i -= -i&i
        return ans
    
    def query(self, l, r):
        if l == 0:
            return self.sum(r-1)
        else:
            return self.sum(r-1)-self.sum(l-1)
    
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.bit[i] += x
            i += -i&i

・線分の交差判定
def judge(ax, ay, bx, by, cx, cy, dx, dy):
    s = (ax-bx)*(cy-ay)-(ay-by)*(cx-ax)
    t = (ax-bx)*(dy-ay)-(ay-by)*(dx-ax)
    if s*t > 0:
        return False
    s = (cx-dx)*(ay-cy)-(cy-dy)*(ax-cx)
    t = (cx-dx)*(by-cy)-(cy-dy)*(bx-cx)
    if s*t > 0:
        return False
    return True

・二次元累積和
class cum2:
    def __init__(self, A):
        self.cum = [[0]*(len(A[0])+1) for _ in range(len(A)+1)]
        for i in range(len(A)):
            for j in range(len(A[0])):
                self.cum[i+1][j+1] = A[i][j]
        for i in range(1, len(A)+1):
            for j in range(2, len(A[0])+1):
                self.cum[i][j] += self.cum[i][j-1]
        for i in range(2, len(A)+1):
            for j in range(1, len(A[0])+1):
                self.cum[i][j] += self.cum[i-1][j]
    def query(self, lh, rh, lw, rw):
        return self.cum[rh+1][rw+1]+self.cum[lh][lw]-self.cum[rh+1][lw]-self.cum[lh][rw+1]

・三次元累積和
class cum3:
    def __init__(self, A):
        self.cum = [[[0]*(len(A[0][0])+1) for _ in range(len(A[0])+1)] for _ in range(len(A)+1)]
        for i in range(len(A)):
            for j in range(len(A[0])):
                for k in range(len(A[0][0])):
                    self.cum[i+1][j+1][k+1] = A[i][j][k]
        for i in range(1, len(A)+1):
            for j in range(1, len(A[0])+1):
                for k in range(2, len(A[0][0])+1):
                    self.cum[i][j][k] += self.cum[i][j][k-1]
        for i in range(1, len(A)+1):
            for j in range(2, len(A[0])+1):
                for k in range(1, len(A[0][0])+1):
                    self.cum[i][j][k] += self.cum[i][j-1][k]
        for i in range(2, len(A)+1):
            for j in range(1, len(A[0])+1):
                for k in range(1, len(A[0][0])+1):
                    self.cum[i][j][k] += self.cum[i-1][j][k]
    def query(self, lh, rh, ld, rd, lw, rw):
        return (self.cum[rh+1][rd+1][rw+1]+self.cum[rh+1][ld][lw]-self.cum[rh+1][rd+1][lw]-self.cum[rh+1][ld][rw+1]
                -self.cum[lh][rd+1][rw+1]-self.cum[lh][ld][lw]+self.cum[lh][rd+1][lw]+self.cum[lh][ld][rw+1])

・LowLink
class LowLink:
    def __init__(self, N):
        self.N = N
        self.M = 0
        self.G = [[] for _ in range(N)]
    
    def add_edge(self, u, v):
        self.G[u].append((v, self.M))
        self.G[v].append((u, self.M))
        self.M += 1
    
    @bootstrap
    def dfs(self, n, parent):
        self.visited[n] = True
        self.ord[n], self.low[n] = self.cnt, self.cnt
        self.cnt += 1
        is_ap = False
        child = 0
        for v, idx in self.G[n]:
            if not self.visited[v]:
                child += 1
                yield self.dfs(v, idx)
                self.low[n] = min(self.low[n], self.low[v])
                if parent != -1 and self.ord[n] <= self.low[v]:
                    is_ap = True
                if self.ord[n] < self.low[v]:
                    self.bridge.append(idx)
            elif idx != parent:
                self.low[n] = min(self.low[n], self.ord[v])
        if parent == -1 and 2 <= child:
            is_ap = True
        if is_ap:
            self.articulation_points.append(n)
        yield

    def find(self):
        self.ord = [-1]*self.N
        self.low = [-1]*self.N
        self.visited = [False]*self.N
        self.cnt = 0
        self.articulation_points = []
        self.bridge = []
        for i in range(self.N):
            if not self.visited[i]:
                self.dfs(i, -1)
        return sorted(self.articulation_points), sorted(self.bridge)

・Trie木
class Trie:
    def __init__(self, N, type):
        self.tree = [[-1]*26 for _ in range(N+1)]
        self.arrive = [0]*(N+1)
        self.last = [0]*(N+1)
        self.nex = 1
        if type == 0:
            self.base = ord("a")
        else:
            self.base = ord("A")
    
    def insert(self, S):
        now = 0
        self.arrive[now] += 1
        for s in S:
            if self.tree[now][ord(s)-self.base] == -1:
                self.tree[now][ord(s)-self.base] = self.nex
                now = self.nex
                self.nex += 1
            else:
                now = self.tree[now][ord(s)-self.base]
            self.arrive[now] += 1
        self.last[now] += 1
    
    def search(self, S):
        now = 0
        for s in S:
            if self.tree[now][ord(s)-self.base] == -1:
                return 0
            now = self.tree[now][ord(s)-self.base]
        return self.last[now]
    
    def start_with(self, S):
        now = 0
        for s in S:
            if self.tree[now][ord(s)-self.base] == -1:
                return 0
            now = self.tree[now][ord(s)-self.base]
        return self.arrive[now]

    def count(self):
        return self.arrive[0]

・分割
# dp[i][j] jをi以下の数字で分割する個数
def division1(n):
    dp = [[0]*(n+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        for j in range(n+1):
            if j-i >= 0:
                dp[i][j] = (dp[i-1][j]+dp[i][j-i])%MOD
            else:
                dp[i][j] = dp[i-1][j]
    return dp
# dp[i][j] iを長さがjの数字に分割する個数
def division2(n):
    dp = [[0]*(n+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i-j >= 0:
                dp[i][j] = (dp[i-1][j-1]+dp[i-j][j])%MOD
            else:
                dp[i][j] = dp[i-1][j-1]
    return dp
# dp[i][j] iを長さがj以下の数字に分割する個数
def division3(n):
    dp = [[0]*(n+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i-j >= 0:
                dp[i][j] = (dp[i][j-1]+dp[i-j][j])%MOD
            else:
                dp[i][j] = dp[i][j-1]
    return dp

・SortedSet(tatyam)
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, List, Tuple, TypeVar, Optional
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) -> Optional[T]:
        "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) -> Optional[T]:
        "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) -> Optional[T]:
        "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) -> Optional[T]:
        "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

・SortedMultiSet(tatyam)
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, List, Tuple, TypeVar, Optional
T = TypeVar('T')

class SortedMultiset(Generic[T]):
    BUCKET_RATIO = 16
    SPLIT_RATIO = 24
    
    def __init__(self, a: Iterable[T] = []) -> None:
        "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
        a = list(a)
        n = self.size = len(a)
        if any(a[i] > a[i + 1] for i in range(n - 1)):
            a.sort()
        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 "SortedMultiset" + 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 count(self, x: T) -> int:
        "Count the number of x."
        return self.index_right(x) - self.index(x)

    def add(self, x: T) -> None:
        "Add an element. / O(√N)"
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return
        a, b, i = self._position(x)
        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:]]
    
    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) -> Optional[T]:
        "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) -> Optional[T]:
        "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) -> Optional[T]:
        "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) -> Optional[T]:
        "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

・区間更新 区間和取得
class Node:
    def __init__(self, value, size):
        self.value = value
        self.size = size

def op(left, right):
    return Node(left.value+right.value, left.size+right.size)

def mapping(top, bottom):
    if top != INF:
        return Node(top*bottom.size, bottom.size)
    else:
        return bottom

def composition(top, bottom):
    if top != INF:
        return top
    else:
        return bottom

e = Node(0, 0)
ID = INF

・木の重心
@bootstrap
def dfs(n, pre):
    cnt = 1
    MAX = -(10**18)
    for i, v in enumerate(G[n]):
        if v != pre:
            c = yield dfs(v, n)
            cnt += c
            if MAX < c:
                MAX = c
                maxidx[n] = i
    size[n] = cnt
    yield size[n]

size = [-1]*N
maxidx = [-1]*N
dfs(0, -1)

@bootstrap
def dfs2(n):
    if size[G[n][maxidx[n]]] > N//2:
        yield (yield dfs2(G[n][maxidx[n]]))
    yield n

center = dfs2(0)

・3点を結ぶ三角形の面積
def area(x1, y1, x2, y2, x3, y3):
    return abs((x1-x3)*(y2-y3)-(x2-x3)*(y1-y3))/2

・ChatGPT用
The following code is what I wrote to solve a problem in an AtCoder contest. When using generative AI to translate programming languages during an ongoing AtCoder contest, there are the following restrictions: "It is absolutely necessary to include the original code at the beginning of the submission as a comment or similar." "Only translations that do not alter the algorithm are permitted. In particular, any changes that would affect the time complexity are strictly prohibited." For any parts that cannot be directly translated, please mark them as "FAILED" and leave them unconverted. Following these strict AtCoder rules, please translate the following code from Python to C++.

・文字と数字の変換
def code(s):
    return ord(s)-ord("a")
def codeR(n):
    return chr(ord("a")+n)

・組み合わせの数（k == 2 or k == 3）
def nC2(n):
    return n*(n-1)//2
def nC3(n):
    return n*(n-1)*(n-2)//6

・無限等比級数の和
def infinite(a, r):
    # a = 初項 r = 公比
    return inverse(a, 1-r)

・UnionFind（値を保持）
class UnionFind:
    def __init__(self, n, A):
        self.n = n
        self.parent_size = [-1]*n
        self.A = A[:]
 
    def leader(self, a):
        if self.parent_size[a] < 0:
            return a
        self.parent_size[a] = self.leader(self.parent_size[a])
        return self.parent_size[a]
 
    def merge(self, a, b):
        x, y = self.leader(a), self.leader(b)
        if x == y:
            return 
        a = self.A[x]
        if abs(self.parent_size[x]) < abs(self.parent_size[y]):
            x, y = y, x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y] = x
        self.A[x] = a
        return 
    
    def __getitem__(self, n):
        return self.A[self.leader(n)]
    
    def update(self, n, a):
        self.A[self.leader(n)] = a
 
    def same(self, a, b):
        return self.leader(a) == self.leader(b)
 
    def size(self, a):
        return abs(self.parent_size[self.leader(a)])
 
    def groups(self):
        result = [[] for _ in range(self.n)]
        for i in range(self.n):
            result[self.leader(i)].append(i)
        return [r for r in result if r != []]

・UnionFind（値を演算）
def op(x, y):
    return 
class UnionFind:
    def __init__(self, n, A, op):
        self.n = n
        self.parent_size = [-1]*n
        self.A = A[:]
        self.op = op
 
    def leader(self, a):
        if self.parent_size[a] < 0:
            return a
        self.parent_size[a] = self.leader(self.parent_size[a])
        return self.parent_size[a]
 
    def merge(self, a, b):
        x, y = self.leader(a), self.leader(b)
        if x == y:
            return 
        l, r = self.A[x], self.A[y]
        if abs(self.parent_size[x]) < abs(self.parent_size[y]):
            x, y = y, x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y] = x
        self.A[x] = self.op(l, r)
        return 
    
    def __getitem__(self, n):
        return self.A[self.leader(n)]
    
    def update(self, n, a):
        self.A[self.leader(n)] = a
 
    def same(self, a, b):
        return self.leader(a) == self.leader(b)
 
    def size(self, a):
        return abs(self.parent_size[self.leader(a)])
 
    def groups(self):
        result = [[] for _ in range(self.n)]
        for i in range(self.n):
            result[self.leader(i)].append(i)
        return [r for r in result if r != []]

・ランレングス圧縮
def RLE(A):
    ans = []
    cnt = 0
    for i in range(len(A)):
        cnt += 1
        if i+1 == len(A) or A[i] != A[i+1]:
            ans.append((A[i], cnt))
            cnt = 0
    return ans

def RLER(A):
    ans = []
    for s, c in A:
        ans.append(s*c)
    return "".join(ans)

・Manacher
def Manacher(S):
    C = [""]
    for s in S:
        C.append(s)
        C.append("")
    R = [0]*len(C)
    i = 0
    j = 0
    while i < len(C):
        while 0 <= i-j and i+j < len(C) and C[i-j] == C[i+j]:
            j += 1
        R[i] = j
        k = 1
        while 0 <= i-k and k+R[i-k] < j:
            R[i+k] = R[i-k]
            k += 1
        i += k
        j -= k
    odd = []
    even = []
    for i in range(1, len(C)-1):
        if i%2 == 1:
            odd.append(R[i]//2)
        else:
            even.append(R[i]//2)
    return odd, even

・凸包
def cross3(a, b, c):
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

def convex_hull(ps):
    ps.sort()
    qs = []
    L = len(ps)
    for p in ps:
        # 一直線上で高々2点にする場合は ">=" にする
        while len(qs) > 1 and cross3(qs[-1], qs[-2], p) > 0:
            qs.pop()
        qs.append(p)
    t = len(qs)
    for i in range(L-2, -1, -1):
        p = ps[i]
        while len(qs) > t and cross3(qs[-1], qs[-2], p) > 0:
            qs.pop()
        qs.append(p)
    return qs

A = []
IN = [-1]*N
OUT = [-1]*N
dfs(0, -1, 0)

・Auxiliary Tree
class AuxiliaryTree:
    def __init__(self, N, G):
        self.N = N
        self.G = G
        self.IN = [0]*N
        self.OUT = [0]*N
        self.depth = [0]*N
        self.E = []
        self.dfs(0, -1, 0)
        self.L = len(self.E)
        self.lg = [0]*(self.L+1)
        self.make_sparse_table()

    @bootstrap
    def dfs(self, n, p, d):
        self.depth[n] = d
        self.IN[n] = len(self.E)
        self.E.append(n)
        for v in self.G[n]:
            if v == p:
                continue
            yield self.dfs(v, n, d+1)
            self.E.append(n)
        self.OUT[n] = len(self.E)
        self.E.append(n)
        yield
    
    def make_sparse_table(self):
        for i in range(2, self.L+1):
            self.lg[i] = self.lg[i>>1]+1
        self.st = [[self.L]*(self.L-(1<<i)+1) for i in range(self.lg[self.L]+1)]
        self.st[0] = self.E[:]
        b = 1
        for i in range(self.lg[self.L]):
            for j in range(self.L-(b<<1)+1):
                self.st[i+1][j] = (self.st[i][j] if self.depth[self.st[i][j]] <= self.depth[self.st[i][j+b]] else self.st[i][j+b])
            b <<= 1
    
    def lca(self, u, v):
        x, y = self.IN[u], self.IN[v]
        l = self.lg[y-x+1]
        return self.st[l][x] if self.depth[self.st[l][x]] <= self.depth[self.st[l][y-(1<<l)+1]] else self.st[l][y-(1<<l)+1]
    
    def query(self, v):
        nG = defaultdict(list)
        V = v[:]
        V.sort(key=self.IN.__getitem__)
        K = len(V)
        stack = [V[0]]
        for i in range(K-1):
            w = self.lca(V[i], V[i+1])
            if w != V[i]:
                last = stack.pop()
                while stack and self.depth[w] < self.depth[stack[-1]]:
                    d = abs(self.depth[stack[-1]]-self.depth[last])
                    nG[stack[-1]].append((last, d))
                    nG[last].append((stack[-1], d))
                    last = stack.pop()
                if not stack or stack[-1] != w:
                    stack.append(w)
                    V.append(w)
                d = abs(self.depth[w]-self.depth[last])
                nG[w].append((last, d))
                nG[last].append((w, d))
            stack.append(V[i+1])
        for i in range(len(stack)-1):
            d = abs(self.depth[stack[i]]-self.depth[stack[i+1]])
            nG[stack[i]].append((stack[i+1], d))
            nG[stack[i+1]].append((stack[i], d))
        return nG, stack[0]

・木の直径と重心
visited = [-1]*N
visited[0] = 0
que = deque()
que.append(0)
while que:
    n = que.popleft()
    for v in G[n]:
        if visited[v] == -1:
            visited[v] = visited[n]+1
            que.append(v)
idx = visited.index(max(visited))
visited = [-1]*N
visited[idx] = 0
pre = [-1]*N
que = deque()
que.append(idx)
while que:
    n = que.popleft()
    for v in G[n]:
        if visited[v] == -1:
            visited[v] = visited[n]+1
            que.append(v)
            pre[v] = n
D = max(visited)
idx = visited.index(D)
while visited[idx] > (D+1)//2:
    idx = pre[idx]
center1 = idx
center2 = -1
if D%2 == 1:
    center2 = pre[idx]

・高速フーリエ変換
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]

・分数
from math import gcd

class Fraction:
    def __init__(self, top, bottom):
        if bottom == 0:
            raise ZeroDivisionError
        GCD = gcd(top, bottom)
        if bottom < 0:
            top = -top
            bottom = -bottom
        self.top = top//GCD
        self.bottom = bottom//GCD

    def _to_fraction(self, x):
        return x if isinstance(x, Fraction) else Fraction(x, 1)

    def __eq__(self, other):
        other = self._to_fraction(other)
        return self.top == other.top and self.bottom == other.bottom
    
    def __ne__(self, other):
        other = self._to_fraction(other)
        return self.top != other.top or self.bottom != other.bottom
    
    def __lt__(self, other):
        other = self._to_fraction(other)
        return self.top*other.bottom < self.bottom*other.top
    
    def __le__(self, other):
        other = self._to_fraction(other)
        return self.top*other.bottom <= self.bottom*other.top
    
    def __gt__(self, other):
        other = self._to_fraction(other)
        return self.top*other.bottom > self.bottom*other.top
    
    def __ge__(self, other):
        other = self._to_fraction(other)
        return self.top*other.bottom >= self.bottom*other.top
        
    def __add__(self, other):
        other = self._to_fraction(other)
        GCD = gcd(self.bottom, other.bottom)
        bottom = self.bottom*other.bottom//GCD
        top1 = self.top*(bottom//self.bottom)
        top2 = other.top*(bottom//other.bottom)
        return Fraction(top1+top2, bottom)

    def __sub__(self, other):
        other = self._to_fraction(other)
        GCD = gcd(self.bottom, other.bottom)
        bottom = self.bottom*other.bottom//GCD
        top1 = self.top*(bottom//self.bottom)
        top2 = other.top*(bottom//other.bottom)
        return Fraction(top1-top2, bottom)

    def __mul__(self, other):
        other = self._to_fraction(other)
        return Fraction(self.top*other.top, self.bottom*other.bottom)
    
    def __truediv__(self, other):
        other = self._to_fraction(other)
        return Fraction(self.top*other.bottom, self.bottom*other.top)
    
    def __radd__(self, other):
        return self+other
    
    def __rsub__(self, other):
        return self._to_fraction(other)-self
    
    def __rmul__(self, other):
        return self*other
    
    def __rtruediv__(self, other):
        return self._to_fraction(other)/self
    
    def __int__(self):
        return self.top//self.bottom
    
    def __float__(self):
        return self.top/self.bottom
    
    def __str__(self):
        return f"{self.top}/{self.bottom}"
    
    def __hash__(self):
        return hash((self.top, self.bottom))
    
    def __bool__(self):
        return self.top != 0
    
    def __neg__(self):
        return Fraction(-self.top, self.bottom)
    
    def __abs__(self):
        return Fraction(abs(self.top), self.bottom)
    
    def get(self):
        return self.top, self.bottom

・ランダムチェッカー
from random import randrange

def solve1(N, L, R, A):
    # 自分のプログラム
    pass

def solve2(N, L, R, A):
    # 愚直のプログラム
    pass

while True:
    # 入力データをランダムで生成する
    
    # 違う出力をした場合に出力して終了する
    if solve1() != solve2():
        break

・floor_sum
def floor_sum(n, m, a, b):
    ans = 0
    while True:
        if a >= m or a < 0:
            ans += n * (n - 1) * (a // m) // 2
            a %= m
        if b >= m or b < 0:
            ans += n * (b // m)
            b %= m
        y_max = a * n + b
        if y_max < m: break
        n, b, m, a = y_max // m, y_max % m, a, m
    return ans

・ハッシュ（Hack対策）
from random import randrange

H = randrange(1, 1<<60)
def Hash(n):
    return n^H

・ChatGPT 翻訳依頼
今からCodeforcesの問題文を与えるため、日本語に翻訳してください。
翻訳以外の用途で生成AIを使用することは禁止されているため、問題の解法については出力しないようにしてください。

・Convex Hull Trick（O(N)）
class Convex_Hull_Trick:
    def __init__(self):
        self.que = deque()

    def check(self, f1, f2, f3):
        return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])
    
    def f(self, f1, x):
        return f1[0]*x + f1[1]
    
    # add f_i(x) = a*x + b
    # 降順
    def add_line(self, a, b):
        f1 = (a, b)
        while len(self.que) >= 2 and self.check(self.que[-2], self.que[-1], f1):
            self.que.pop()
        self.que.append(f1)

    # min f_i(x)
    # 昇順
    def query(self, x):
        while len(self.que) >= 2 and self.f(self.que[0], x) >= self.f(self.que[1], x):
            self.que.popleft()
        return self.f(self.que[0], x)

・セグメント木（区間演算、一点取得）
def op(x, y):
    return 
class SegTree:
    def __init__(self, init_val, op, ide_ele):
        n = len(init_val)
        self.n = n
        self.op = op
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]

    def update(self, l, r, x):
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.tree[l] = self.op(x, self.tree[l])
                l += 1
            if r & 1:
                self.tree[r - 1] = self.op(x, self.tree[r - 1])
            l >>= 1
            r >>= 1

    def query(self, k):
        ans = self.ide_ele
        k += self.num
        ans = self.op(ans, self.tree[k])
        while k > 1:
            ans = self.op(ans, self.tree[k>>1])
            k >>= 1
        return ans

・セグメント木（区間更新、一点取得）
class SegTree:
    def __init__(self, init_val):
        n = len(init_val)
        self.n = n
        self.num = 1 << (n - 1).bit_length()
        self.tree = [-1] * 2 * self.num
        self.rank = [-1] * 2 * self.num
        self.cnt = 0
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
            self.rank[self.num + i] = self.cnt
        self.cnt += 1

    def update(self, l, r, x):
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.tree[l] = x
                self.rank[l] = self.cnt
                l += 1
            if r & 1:
                self.tree[r - 1] = x
                self.rank[r - 1] = self.cnt
            l >>= 1
            r >>= 1
        self.cnt += 1

    def query(self, k):
        k += self.num
        ans = self.tree[k]
        MAX = self.rank[k]
        while k > 1:
            if MAX < self.rank[k>>1]:
                ans = self.tree[k>>1]
                MAX = self.rank[k>>1]
            k >>= 1
        return ans

・区間XOR
def XORSUM(n):
    if n%4 == 0:
        return n
    elif n%4 == 1:
        return 1
    elif n%4 == 2:
        return n+1
    else:
        return 0

def rangeXOR(l, r):
    return XORSUM(r)^XORSUM(l-1)

・BucketList(tatyam)
# https://github.com/tatyam-prime/SortedSet/blob/main/BucketList.py
import math
from typing import Generic, Iterable, Iterator, TypeVar
T = TypeVar('T')

class BucketList(Generic[T]):
    BUCKET_RATIO = 16
    SPLIT_RATIO = 24
    
    def __init__(self, a: Iterable[T] = []) -> None:
        a = list(a)
        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:
        if len(self) != len(other): return False
        for x, y in zip(self, other):
            if x != y: return False
        return True
    
    def __len__(self) -> int:
        return self.size
    
    def __repr__(self) -> str:
        return "BucketList" + str(self.a)
    
    def __str__(self) -> str:
        return str(list(self))

    def __contains__(self, x: T) -> bool:
        "Return True if x is in the bucket list. / O(N)"
        for y in self:
            if x == y: return True
        return False
    
    def _insert(self, a: list[T], b: int, i: int, x: T) -> None:
        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:]]

    def insert(self, i: int, x: T) -> None:
        "Insert x at the i-th position. / O(√N)"
        if self.size == 0:
            if i != 0 and i != -1: raise IndexError
            self.a = [[x]]
            self.size = 1
            return
        if i < 0:
            for b, a in enumerate(reversed(self.a)):
                i += len(a)
                if i >= 0: return self._insert(a, len(self.a) + ~b, i, x)
        else:
            for b, a in enumerate(self.a):
                if i <= len(a): return self._insert(a, b, i, x)
                i -= len(a)
        raise IndexError

    def append(self, x: T) -> None:
        "Append x to the end of the list. / amortized O(1)"
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return
        a = self.a[-1]
        return self._insert(a, len(self.a) - 1, len(a), x)
    
    def extend(self, a: Iterable[T]) -> None:
        for x in a: self.append(x)
    
    def __getitem__(self, i: int) -> T:
        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, 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 pop(self, i: int = -1) -> T:
        "Remove and return the i-th element. / O(√N) / O(-i) if i < 0"
        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 count(self, x: T) -> int:
        "Return the number of occurrences of x. / O(N)"
        return sum(1 for y in self if x == y)

    def index(self, x: T) -> int:
        "Return the index of the first occurrence of x, raise ValueError if not found. / O(N)"
        for i, y in enumerate(self):
            if x == y: return i
        raise ValueError
    
    def remove(self, x: T) -> None:
        "Remove the first occurrence of x, raise ValueError if not found. / O(N)"
        self.pop(self.index(x))

    def clear(self) -> None:
        self.a = []
        self.size = 0

    def reverse(self) -> None:
        self.a.reverse()
        for a in self.a: a.reverse()

    def copy(self) -> 'BucketList[T]':
        return BucketList(self)

・Lucasの定理
class Lucas:
    def __init__(self, MOD):
        self.MOD = MOD
        self.comb = [[0]*self.MOD for _ in range(self.MOD)]
        self.comb[0][0] = 1
        for i in range(1, self.MOD):
            self.comb[i][0] = 1
            for j in range(1, i+1):
                self.comb[i][j] = (self.comb[i-1][j-1]+self.comb[i-1][j])%self.MOD
    
    def C(self, N, K):
        ans = 1
        while N:
            ans *= self.comb[N%self.MOD][K%self.MOD]
            ans %= self.MOD
            N //= self.MOD
            K //= self.MOD
        return ans

・ラベル
class Label:
    def __init__(self, N, A=[]):
        self.N = N
        if A:
            self.label = A[:]
        else:
            self.label = list(range(N))
        self.labelR = [-1]*self.N
        for i in range(self.N):
            self.labelR[self.label[i]] = i
    
    # ラベルがどの箱に貼られているか
    def __getitem__(self, n):
        return self.labelR[n]
    
    # 箱に貼られているラベルは何か
    def getLabel(self, n):
        return self.label[n]
    
    # ラベルの情報を元にスワップ
    def swap(self, l, r):
        self.label[self.labelR[l]], self.label[self.labelR[r]] = self.label[self.labelR[r]], self.label[self.labelR[l]]
        self.labelR[l], self.labelR[r] = self.labelR[r], self.labelR[l]

・動的セグメントツリー
class Node:
    def __init__(self, init_val):
        self.left = None
        self.right = None
        self.value = init_val
def op(x, y):
    if x[0]%2 == 0:
        return (x[0]+y[0], x[1]+y[1], x[2]+y[2])
    else:
        return (x[0]+y[0], x[1]+y[2], x[2]+y[1])
class DynamicSegmentTree:
    def __init__(self, L, R, op, init_val):
        self.root = Node(init_val)
        self.L = L
        self.R = R
        self.op = op
        self.init_val = init_val
    
    def update(self, idx, value):
        stack = [(self.root, self.L, self.R)]
        path = []
        while stack:
            node, s, e = stack.pop()
            path.append((node, s, e))
            if s == e:
                node.value = value
                break
            mid = (s+e)//2
            if idx <= mid:
                if not node.left:
                    node.left = Node(self.init_val)
                stack.append((node.left, s, mid))
            else:
                if not node.right:
                    node.right = Node(self.init_val)
                stack.append((node.right, mid+1, e))
        path.pop()
        while path:
            node, s, e = path.pop()
            node.value = self.op(node.left.value if node.left else self.init_val, node.right.value if node.right else self.init_val)
    
    def query(self, l, r):
        stack = [(self.root, self.L, self.R)]
        ans = self.init_val
        while stack:
            node, s, e = stack.pop()
            if not node or e < l or r < s:
                continue
            if l <= s and e <= r:
                ans = self.op(ans, node.value)
                continue
            mid = (s+e)//2
            stack.append((node.left, s, mid))
            stack.append((node.right, mid+1, e))
        return ans

・最大流
# https://github.com/not522/ac-library-python/blob/master/atcoder/maxflow.py
from typing import NamedTuple, Optional, List, cast

class MFGraph:
    class Edge(NamedTuple):
        src: int
        dst: int
        cap: int
        flow: int

    class _Edge:
        def __init__(self, dst: int, cap: int) -> None:
            self.dst = dst
            self.cap = cap
            self.rev: Optional[MFGraph._Edge] = None

    def __init__(self, n: int) -> None:
        self._n = n
        self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
        self._edges: List[MFGraph._Edge] = []

    def add_edge(self, src: int, dst: int, cap: int) -> int:
        assert 0 <= src < self._n
        assert 0 <= dst < self._n
        assert 0 <= cap
        m = len(self._edges)
        e = MFGraph._Edge(dst, cap)
        re = MFGraph._Edge(src, 0)
        e.rev = re
        re.rev = e
        self._g[src].append(e)
        self._g[dst].append(re)
        self._edges.append(e)
        return m

    def get_edge(self, i: int) -> Edge:
        assert 0 <= i < len(self._edges)
        e = self._edges[i]
        re = cast(MFGraph._Edge, e.rev)
        return MFGraph.Edge(
            re.dst,
            e.dst,
            e.cap + re.cap,
            re.cap
        )

    def edges(self) -> List[Edge]:
        return [self.get_edge(i) for i in range(len(self._edges))]

    def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
        assert 0 <= i < len(self._edges)
        assert 0 <= new_flow <= new_cap
        e = self._edges[i]
        e.cap = new_cap - new_flow
        assert e.rev is not None
        e.rev.cap = new_flow

    def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> int:
        assert 0 <= s < self._n
        assert 0 <= t < self._n
        assert s != t
        if flow_limit is None:
            flow_limit = cast(int, sum(e.cap for e in self._g[s]))

        current_edge = [0] * self._n
        level = [0] * self._n

        def fill(arr: List[int], value: int) -> None:
            for i in range(len(arr)):
                arr[i] = value

        def bfs() -> bool:
            fill(level, self._n)
            queue = []
            q_front = 0
            queue.append(s)
            level[s] = 0
            while q_front < len(queue):
                v = queue[q_front]
                q_front += 1
                next_level = level[v] + 1
                for e in self._g[v]:
                    if e.cap == 0 or level[e.dst] <= next_level:
                        continue
                    level[e.dst] = next_level
                    if e.dst == t:
                        return True
                    queue.append(e.dst)
            return False

        def dfs(lim: int) -> int:
            stack = []
            edge_stack: List[MFGraph._Edge] = []
            stack.append(t)
            while stack:
                v = stack[-1]
                if v == s:
                    flow = min(lim, min(e.cap for e in edge_stack))
                    for e in edge_stack:
                        e.cap -= flow
                        assert e.rev is not None
                        e.rev.cap += flow
                    return flow
                next_level = level[v] - 1
                while current_edge[v] < len(self._g[v]):
                    e = self._g[v][current_edge[v]]
                    re = cast(MFGraph._Edge, e.rev)
                    if level[e.dst] != next_level or re.cap == 0:
                        current_edge[v] += 1
                        continue
                    stack.append(e.dst)
                    edge_stack.append(re)
                    break
                else:
                    stack.pop()
                    if edge_stack:
                        edge_stack.pop()
                    level[v] = self._n
            return 0

        flow = 0
        while flow < flow_limit:
            if not bfs():
                break
            fill(current_edge, 0)
            while flow < flow_limit:
                f = dfs(flow_limit - flow)
                flow += f
                if f == 0:
                    break
        return flow

    def min_cut(self, s: int) -> List[bool]:
        visited = [False] * self._n
        stack = [s]
        visited[s] = True
        while stack:
            v = stack.pop()
            for e in self._g[v]:
                if e.cap > 0 and not visited[e.dst]:
                    visited[e.dst] = True
                    stack.append(e.dst)
        return visited

・Gauss-Jordanの掃き出し法（MOD）
def GaussJordan_MOD(A, is_extended):
    H, W = len(A), len(A[0])

    for i in range(H):
        for j in range(W):
            A[i][j] %= MOD

    rank = 0
    for j in range(W-is_extended):
        for i in range(rank, H):
            if A[i][j] != 0:
                pivot = i
                break
        else:
            continue
        A[pivot], A[rank] = A[rank], A[pivot]
        inv = pow(A[rank][j], -1, MOD)
        for i in range(W):
            A[rank][i] *= inv
            A[rank][i] %= MOD
        for i in range(H):
            if i == rank or A[i][j] == 0:
                continue
            mul = A[i][j]
            for k in range(W):
                A[i][k] -= A[rank][k]*mul%MOD
                A[i][k] %= MOD
        rank += 1

    return rank

・連立方程式（GaussJordan）
def linear_equation(A, B):
    H, W = len(A), len(A[0])
    for i in range(H):
        A[i].append(B[i])

    rank = GaussJordan_MOD(A, True)
    for i in range(rank, H):
        if A[i][W]:
            return None, None
    
    ans = [A[i][W] for i in range(rank)]
    C = A[:rank]
    for i in range(rank):
        C[i].pop()
    return C, ans

・二項係数（Nが大きいとき用）
def C(N, K):
    if N < K:
        return 0
    if N < K*2:
        K = N-K
    top = 1
    for i in range(N, N-K, -1):
        top *= i
        top %= MOD
    bottom = 1
    for i in range(1, K+1):
        bottom *= i
        bottom %= MOD
    return inverse(top, bottom)

・BinaryTrie
class BinaryTrie:
    def __init__(self, length):
        self.tree = [[-1]*2]
        self.arrive = [0]
        self.last = [0]
        self.nex = 1
        self.length = length
        self.all_xor = 0
    
    def BIT(self, bit, n):
        return bit>>n & 1
    
    def operate_xor(self, n):
        self.all_xor ^= n
    
    def count(self):
        return self.arrive[0]

    def find(self, n):
        now = 0
        for i in reversed(range(self.length)):
            nex = self.BIT(n, i)^self.BIT(self.all_xor, i)
            if self.tree[now][nex] != -1 and 1 <= self.arrive[self.tree[now][nex]]:
                now = self.tree[now][self.BIT(n, i)^self.BIT(self.all_xor, i)]
            else:
                return False
        return True
    
    def insert(self, n):
        now = 0
        self.arrive[now] += 1
        for i in reversed(range(self.length)):
            if self.tree[now][self.BIT(n, i)^self.BIT(self.all_xor, i)] == -1:
                self.tree[now][self.BIT(n, i)^self.BIT(self.all_xor, i)] = self.nex
                self.tree.append([-1]*2)
                self.arrive.append(0)
                self.last.append(0)
                now = self.nex
                self.nex += 1
            else:
                now = self.tree[now][self.BIT(n, i)^self.BIT(self.all_xor, i)]
            self.arrive[now] += 1
        self.last[now] += 1

    def delete(self, n):
        # 存在していることが前提
        now = 0
        self.arrive[now] -= 1
        for i in reversed(range(self.length)):
            now = self.tree[now][self.BIT(n, i)^self.BIT(self.all_xor, i)]
            self.arrive[now] -= 1
        self.last[now] -= 1
    
    def min_element(self, n=0):
        if self.count() == 0:
            return -1
        ans = 0
        now = 0
        for i in reversed(range(self.length)):
            bit = self.BIT(n, i)^self.BIT(self.all_xor, i)
            nex = self.tree[now][bit]
            if nex != -1 and 1 <= self.arrive[nex]:
                now = nex
                if bit:
                    ans |= 1<<i
            else:
                now = self.tree[now][bit^1]
                if not bit:
                    ans |= 1<<i
        return ans^self.all_xor
    
    def max_element(self, n=0):
        if self.count() == 0:
            return -1
        ans = 0
        now = 0
        for i in reversed(range(self.length)):
            bit = self.BIT(n, i)^self.BIT(self.all_xor, i)^1
            nex = self.tree[now][bit]
            if nex != -1 and 1 <= self.arrive[nex]:
                now = nex
                if bit:
                    ans |= 1<<i
            else:
                now = self.tree[now][bit^1]
                if not bit:
                    ans |= 1<<i
        return ans^self.all_xor
    
    def kth_smallest(self, k, n=0):
        k += 1
        if self.count() < k:
            return -1
        ans = 0
        now = 0
        for i in reversed(range(self.length)):
            bit = self.BIT(n, i)^self.BIT(self.all_xor, i)
            nex = self.tree[now][bit]
            if nex != -1 and k <= self.arrive[nex]:
                now = nex
                if bit:
                    ans |= 1<<i
            else:
                now = self.tree[now][bit^1]
                k -= self.arrive[nex] if nex != -1 else 0
                if not bit:
                    ans |= 1<<i
        return ans^self.all_xor
    
    def kth_largest(self, k, n=0):
        k += 1
        if self.count() < k:
            return -1
        ans = 0
        now = 0
        for i in reversed(range(self.length)):
            bit = self.BIT(n, i)^self.BIT(self.all_xor, i)^1
            nex = self.tree[now][bit]
            if nex != -1 and k <= self.arrive[nex]:
                now = nex
                if bit:
                    ans |= 1<<i
            else:
                now = self.tree[now][bit^1]
                k -= self.arrive[nex] if nex != -1 else 0
                if not bit:
                    ans |= 1<<i
        return ans^self.all_xor
    
    def freq(self, n):
        now = 0
        for i in reversed(range(self.length)):
            bit = self.BIT(n, i)^self.BIT(self.all_xor, i)
            if self.tree[now][bit] == -1:
                return 0
            now = self.tree[now][bit]
        return self.last[now]

・直線の方程式
def line_equation(x1, y1, x2, y2):
    a = y2-y1
    b = x1-x2
    c = x2*y1-x1*y2
    return a, b, c

・IntervalSet
class IntervalSet:
    def __init__(self):
        self.interval = SortedMultiset()
    
    def add(self, l, r):
        idx = self.interval.index((l, -1))
        cnt = r-l+1
        if 1 <= idx and l <= self.interval[idx-1][1]+1:
            l2, r2 = self.interval.pop(idx-1)
            cnt -= min(r2, r)-l+1
            idx -= 1
            l = l2
            r = max(r2, r)
        while idx < len(self.interval) and self.interval[idx][0] <= r+1:
            l2, r2 = self.interval.pop(idx)
            cnt -= min(r2, r)-l2+1
            r = max(r, r2)
        self.interval.add((l, r))
        return cnt

    def remove(self, l, r):
        idx = self.interval.index((l, -1))
        cnt = 0
        if 1 <= idx and l <= self.interval[idx-1][1]:
            l2, r2 = self.interval.pop(idx-1)
            cnt += min(r, r2)-l+1
            self.interval.add((l2, l-1))
            if r < r2:
                self.interval.add((r+1, r2))
        while idx < len(self.interval) and self.interval[idx][0] <= r:
            l2, r2 = self.interval.pop(idx)
            cnt += min(r2, r)-l2+1
            if r < r2:
                self.interval.add((r+1, r2))
        return cnt
    
    def add2(self, l, r):
        ans = []
        idx = self.interval.index((l, -1))
        pl = l
        if 1 <= idx and l <= self.interval[idx-1][1]+1:
            l2, r2 = self.interval.pop(idx-1)
            idx -= 1
            l = l2
            r = max(r2, r)
            pl = r2+1
        while idx < len(self.interval) and self.interval[idx][0] <= r+1:
            l2, r2 = self.interval.pop(idx)
            if pl < l2:
                ans.append((pl, l2-1))
            pl = r2+1
            r = max(r, r2)
        self.interval.add((l, r))
        if pl <= r:
            ans.append((pl, r))
        return ans

    def remove2(self, l, r):
        ans = []
        idx = self.interval.index((l, -1))
        if 1 <= idx and l <= self.interval[idx-1][1]:
            l2, r2 = self.interval.pop(idx-1)
            self.interval.add((l2, l-1))
            ans.append((l, min(r2, r)))
            if r < r2:
                self.interval.add((r+1, r2))
        while idx < len(self.interval) and self.interval[idx][0] <= r:
            l2, r2 = self.interval.pop(idx)
            ans.append((l2, min(r2, r)))
            if r < r2:
                self.interval.add((r+1, r2))
        return ans
    
    def find(self, x):
        idx = self.interval.index((x+1, -1))
        if idx == 0:
            return (-1, -1)
        l, r = self.interval[idx-1]
        if x <= r:
            return (l, r)
        else:
            return (-1, -1)

・Mo's algorithm
class Mo:
    def __init__(self, N, add_L, add_R, remove_L, remove_R, route=None):
        self.N = N
        self.add_L = add_L
        self.add_R = add_R
        self.remove_L = remove_L
        self.remove_R = remove_R
        self.route = route if route is not None else int(self.N**0.5)+1
    
    def solve(self, query):
        Q = len(query)
        bucket = [[] for _ in range(self.N//self.route+1)]
        for i, (l, r) in enumerate(query):
            l, r = l-1, r-1
            bucket[l//self.route].append((i, l, r))
        
        ans = [-1]*Q
        now = 0
        left = 0
        right = -1
        for idx, q in enumerate(bucket):
            for i, l, r in sorted(q, key=lambda x:x[2], reverse=idx%2):
                while l < left:
                    left -= 1
                    now = self.add_L(now, left)
                while right < r:
                    right += 1
                    now = self.add_R(now, right)
                while left < l:
                    now = self.remove_L(now, left)
                    left += 1
                while r < right:
                    now = self.remove_R(now, right)
                    right -= 1
                ans[i] = now
        return ans

・Baby-step Giant-step
def BSGS(A, G, P):
    route = isqrt(P)+1
    D = dict()
    SUM = 1
    for i in range(route):
        if SUM not in D:
            D[SUM] = i
        SUM *= A
        SUM %= P
    C = pow(A, -route, P)
    for i in range(route):
        if G in D:
            return route*i+D[G]
        G *= C
        G %= P
    else:
        return -1

・DSU on Tree
@bootstrap
def get_size(n, p):
    for v in G[n]:
        if v == p:
            continue
        yield get_size(v, n)
        size[n] += size[v]
    yield

size = [1]*N
get_size(0, -1)

@bootstrap
def dfs(n, p, keep):
    MAX, bigv = -1, -1
    for v in G[n]:
        if v == p:
            continue
        if MAX < size[v]:
            MAX = size[v]
            bigv = v
    for v in G[n]:
        if v == p or v == bigv:
            continue
        yield dfs(v, n, 0)
    if bigv != -1:
        yield dfs(bigv, n, 1)
        A[n] = A[bigv]
    for v in G[n]:
        if v == p or v == bigv:
            continue
        for x in A[v]:
            A[n].append(x)
    A[n].append(n)
    if keep == 0:
        for v in A[n]:
            pass
    yield

A = [[] for _ in range(N)]
dfs(0, -1, 0)

・Suffix Automaton
class SuffixAutomaton:
    class Node:
        def __init__(self, nex, link, size):
            self.nex = nex
            self.link = link
            self.size = size
    def __init__(self, type):
        self.nodes = [self.Node([-1]*26, -1, 0)]
        self.ord_a = ord("a") if not type else ord("A")
        self.last = 0
    
    def alpha_code(self, s):
        return ord(s)-self.ord_a
    
    def push(self, c):
        new_node = len(self.nodes)
        code = self.alpha_code(c)
        self.nodes.append(self.Node([-1]*26, -1, self.nodes[self.last].size+1))
        p = self.last
        while p != -1 and self.nodes[p].nex[code] == -1:
            self.nodes[p].nex[code] = new_node
            p = self.nodes[p].link
        q = 0 if p == -1 else self.nodes[p].nex[code]
        if p == -1 or self.nodes[p].size+1 == self.nodes[q].size:
            self.nodes[new_node].link = q
        else:
            new_q = len(self.nodes)
            self.nodes.append(self.Node(self.nodes[q].nex[:], self.nodes[q].link, self.nodes[p].size+1))
            self.nodes[q].link = new_q
            self.nodes[new_node].link = new_q
            while p != -1 and self.nodes[p].nex[code] == q:
                self.nodes[p].nex[code] = new_q
                p = self.nodes[p].link
        self.last = new_node

・SkewHeap
class SkewHeap:
    class Node:
        __slots__ = ("key", "l", "r")
        def __init__(self, key):
            self.key = key
            self.l = None
            self.r = None

    def __init__(self, isMin=True):
        self.isMin = isMin

    def _comp(self, x, y):
        if self.isMin:
            return x.key < y.key
        else:
            return x.key > y.key

    def meld(self, x, y):
        if not x or not y:
            return x if x else y
        if not self._comp(x, y):
            x, y = y, x
        x.l = self.meld(x.l, y)
        x.l, x.r = x.r, x.l
        return x

    def alloc(self, key):
        return self.Node(key)

    def push(self, x, key):
        return self.meld(x, self.alloc(key))

    def pop(self, x):
        return self.meld(x.l, x.r)

・SkewHeap（遅延加算付き）
class SkewHeap:
    class Node:
        __slots__ = ("key", "laz", "l", "r")
        def __init__(self, key):
            self.key = key
            self.laz = 0
            self.l = None
            self.r = None

    def __init__(self, isMin=True):
        self.isMin = isMin
    
    def _propagate(self, x):
        if x.laz == 0:
            return
        if x.l:
            x.l.laz += x.laz
        if x.r:
            x.r.laz += x.laz
        x.key += x.laz
        x.laz = 0

    def _comp(self, x, y):
        if self.isMin:
            return x.key+x.laz < y.key+y.laz
        else:
            return x.key+x.laz > y.key+y.laz

    def meld(self, x, y):
        if not x or not y:
            return x if x else y
        if not self._comp(x, y):
            x, y = y, x
        self._propagate(x)
        x.l = self.meld(x.l, y)
        x.l, x.r = x.r, x.l
        return x

    def alloc(self, key):
        return self.Node(key)

    def push(self, x, key):
        return self.meld(x, self.alloc(key))

    def pop(self, x):
        self._propagate(x)
        return self.meld(x.l, x.r)
    
    def top(self, x):
        self._propagate(x)
        return x.key
    
    def apply(self, x, laz):
        x.laz += laz
        self._propagate(x)

・Cartesian Tree
def CartesianTree(P):
    stack = []
    child = [[-1]*2 for _ in range(N)]
    parent = [-1]*N
    for i in range(N):
        s = -1
        while stack and P[i] < P[stack[-1]]:
            s = stack.pop()
            child[i][0] = s
        if s != -1:
            parent[s] = i
        if stack:
            parent[i] = stack[-1]
            child[stack[-1]][1] = i
        stack.append(i)
    
    L, R = [-1]*N, [-1]*N
    stack = [(P.index(min(P)), 0, N-1)]
    while stack:
        n, l, r = stack.pop()
        L[n] = l
        R[n] = r
        a, b = child[n]
        if a != -1:
            stack.append((a, l, n-1))
        if b != -1:
            stack.append((b, n+1, r))
    return child, parent, L, R

・ラグランジュ補間（係数）
def lagrange_interpolation_coef(X, Y):
    N = len(X)-1
    for i in range(N+1):
        t = 1
        for j in range(N+1):
            if i != j:
                t *= X[i]-X[j]
                t %= MOD
        Y[i] *= inverse(1, t)
        Y[i] %= MOD

    dp = [0]*(N+2)
    dp[0] = 1
    for i in range(N+1):
        ndp = [0]*(N+2)
        for j in range(N+2):
            ndp[j] += dp[j]*(-X[i])%MOD
            ndp[j] %= MOD
            if 1 <= j:
                ndp[j] += dp[j-1]
                ndp[j] %= MOD
        dp = ndp

    ans = [0]*(N+1)
    invX = []
    for i in range(N+1):
        if X[i] != 0:
            invX.append(inverse(1, X[i]))
        else:
            invX.append(0)
    for i in range(N+1):
        if Y[i] == 0:
            continue
        if X[i] == 0:
            for j in range(N+1):
                ans[j] += dp[j+1]*Y[i]%MOD
                ans[j] %= MOD
        else:
            ans[0] -= dp[0]*invX[i]%MOD*Y[i]%MOD
            ans[0] %= MOD
            pre = (-dp[0])*invX[i]%MOD
            for j in range(1, N+1):
                ans[j] -= (dp[j]-pre)*invX[i]%MOD*Y[i]%MOD
                ans[j] %= MOD
                pre = ((-(dp[j]-pre))*invX[i])%MOD
    return ans

・ラグランジュ補間
def lagrange_interpolation(X, Y, T):
    N = len(X)-1
    ans = 0
    for i in range(N+1):
        t = 1
        t_inv = 1
        for j in range(N+1):
            if i == j:
                continue
            t *= T-X[j]
            t %= MOD
            t_inv *= X[i]-X[j]
            t_inv %= MOD
        ans += inverse(t, t_inv)*Y[i]%MOD
        ans %= MOD
    return ans

・ラグランジュ補間（等差数列）
def lagrange_interpolation_arithmetic(a, d, Y, T):
    # a = Xの初項 d = Xの交差
    N = len(Y)-1
    ans = 0
    ft = 1
    for i in range(N+1):
        ft *= (T-(a+d*i))%MOD
        ft %= MOD
    f = 1
    for i in range(1, N+1):
        f *= -i*d%MOD
        f %= MOD
    ans += inverse(Y[0]*ft%MOD, f*(T-a)%MOD)
    ans %= MOD
    for i in range(N):
        f *= inverse(d*(i+1), d*(i-N))
        f %= MOD
        ans += inverse(Y[i+1]*ft%MOD, f*(T-a-d*(i+1))%MOD)
        ans %= MOD
    return ans

・FPS
# https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp
from array import array

MOD = 998244353
IMAG = 911660635
IIMAG = 86583718
INV2 = 499122177
rate2 = array(
    "I",
    [
        0,
        911660635,
        509520358,
        369330050,
        332049552,
        983190778,
        123842337,
        238493703,
        975955924,
        603855026,
        856644456,
        131300601,
        842657263,
        730768835,
        942482514,
        806263778,
        151565301,
        510815449,
        503497456,
        743006876,
        741047443,
        56250497,
        867605899,
        0,
    ],
)
irate2 = array(
    "I",
    [
        0,
        86583718,
        372528824,
        373294451,
        645684063,
        112220581,
        692852209,
        155456985,
        797128860,
        90816748,
        860285882,
        927414960,
        354738543,
        109331171,
        293255632,
        535113200,
        308540755,
        121186627,
        608385704,
        438932459,
        359477183,
        824071951,
        103369235,
        0,
    ],
)
rate3 = array(
    "I",
    [
        0,
        372528824,
        337190230,
        454590761,
        816400692,
        578227951,
        180142363,
        83780245,
        6597683,
        70046822,
        623238099,
        183021267,
        402682409,
        631680428,
        344509872,
        689220186,
        365017329,
        774342554,
        729444058,
        102986190,
        128751033,
        395565204,
        0,
    ],
)
irate3 = array(
    "I",
    [
        0,
        509520358,
        929031873,
        170256584,
        839780419,
        282974284,
        395914482,
        444904435,
        72135471,
        638914820,
        66769500,
        771127074,
        985925487,
        262319669,
        262341272,
        625870173,
        768022760,
        859816005,
        914661783,
        430819711,
        272774365,
        530924681,
        0,
    ],
)


# https://judge.yosupo.jp/submission/55648
def butterfly(a: list):
    n = len(a)
    h = (n - 1).bit_length()
    le = 0
    while le < h:
        if h - le == 1:
            p = 1 << (h - le - 1)
            rot = 1
            for s in range(1 << le):
                offset = s << (h - le)
                for i in range(p):
                    l = a[i + offset]
                    r = a[i + offset + p] * rot
                    a[i + offset] = (l + r) % MOD
                    a[i + offset + p] = (l - r) % MOD
                rot *= rate2[(~s & -~s).bit_length()]
                rot %= MOD
            le += 1
        else:
            p = 1 << (h - le - 2)
            rot = 1
            for s in range(1 << le):
                rot2 = rot * rot % MOD
                rot3 = rot2 * rot % MOD
                offset = s << (h - le)
                for i in range(p):
                    a0 = a[i + offset]
                    a1 = a[i + offset + p] * rot
                    a2 = a[i + offset + p * 2] * rot2
                    a3 = a[i + offset + p * 3] * rot3
                    a1na3imag = (a1 - a3) % MOD * IMAG
                    a[i + offset] = (a0 + a2 + a1 + a3) % MOD
                    a[i + offset + p] = (a0 + a2 - a1 - a3) % MOD
                    a[i + offset + p * 2] = (a0 - a2 + a1na3imag) % MOD
                    a[i + offset + p * 3] = (a0 - a2 - a1na3imag) % MOD
                rot *= rate3[(~s & -~s).bit_length()]
                rot %= MOD
            le += 2


def butterfly_inv(a: list):
    n = len(a)
    h = (n - 1).bit_length()
    le = h
    while le:
        if le == 1:
            p = 1 << (h - le)
            irot = 1
            for s in range(1 << (le - 1)):
                offset = s << (h - le + 1)
                for i in range(p):
                    l = a[i + offset]
                    r = a[i + offset + p]
                    a[i + offset] = (l + r) % MOD
                    a[i + offset + p] = (l - r) * irot % MOD
                irot *= irate2[(~s & -~s).bit_length()]
                irot %= MOD
            le -= 1
        else:
            p = 1 << (h - le)
            irot = 1
            for s in range(1 << (le - 2)):
                irot2 = irot * irot % MOD
                irot3 = irot2 * irot % MOD
                offset = s << (h - le + 2)
                for i in range(p):
                    a0 = a[i + offset]
                    a1 = a[i + offset + p]
                    a2 = a[i + offset + p * 2]
                    a3 = a[i + offset + p * 3]
                    a2na3iimag = (a2 - a3) * IIMAG % MOD
                    a[i + offset] = (a0 + a1 + a2 + a3) % MOD
                    a[i + offset + p] = (a0 - a1 + a2na3iimag) * irot % MOD
                    a[i + offset + p * 2] = (a0 + a1 - a2 - a3) * irot2 % MOD
                    a[i + offset + p * 3] = (a0 - a1 - a2na3iimag) * irot3 % MOD
                irot *= irate3[(~s & -~s).bit_length()]
                irot %= MOD
            le -= 2


def intt(a):
    if len(a) <= 1:
        return
    butterfly_inv(a)
    iv = pow(len(a), MOD - 2, MOD)
    for i, x in enumerate(a):
        a[i] = x * iv % MOD


def multiply(s: list, t: list):
    n = len(s)
    m = len(t)
    if min(n, m) <= 60:
        a = [0] * (n + m - 1)
        for i in range(n):
            if i & 0b111 == 0:
                for j in range(m):
                    a[i + j] += s[i] * t[j]
                    a[i + j] %= MOD
            else:
                for j in range(m):
                    a[i + j] += s[i] * t[j]
        return [x % MOD for x in a]
    a = s.copy()
    b = t.copy()
    z = 1 << (n + m - 2).bit_length()
    a += [0] * (z - n)
    b += [0] * (z - m)
    butterfly(a)
    butterfly(b)
    for i in range(z):
        a[i] *= b[i]
        a[i] %= MOD
    butterfly_inv(a)
    a = a[: n + m - 1]
    iz = pow(z, MOD - 2, MOD)
    return [v * iz % MOD for v in a]


def pow2(s: list):
    n = len(s)
    l = (n << 1) - 1
    if n <= 60:
        a = [0] * l
        for i, x in enumerate(s):
            for j, y in enumerate(s):
                a[i + j] += x * y
        return [x % MOD for x in a]
    z = 1 << (l - 1).bit_length()
    a = s + [0] * (z - n)
    butterfly(a)
    for i, x in enumerate(a):
        a[i] = x * x % MOD
    butterfly_inv(a)
    a[l:] = []
    iz = pow(z, MOD - 2, MOD)
    return [x * iz % MOD for x in a]


def shrink(a: list):
    while a and not a[-1]:
        a.pop()


def fps_add(a: list, b: list):
    if len(a) < len(b):
        res = b.copy()
        for i, x in enumerate(a):
            res[i] += x
    else:
        res = a.copy()
        for i, x in enumerate(b):
            res[i] += x
    return [x - MOD if MOD <= x else x for x in res]


def fps_sub(a: list, b: list):
    if len(a) < len(b):
        res = b.copy()
        for i, x in enumerate(a):
            res[i] -= x
        return [MOD - x if 0 < x else -x for x in res]
    else:
        res = a.copy()
        for i, x in enumerate(b):
            res[i] -= x
        return [x if 0 <= x else x + MOD for x in res]


def fps_neg(a: list):
    return [MOD - x if x else 0 for x in a]


def fps_div(a: list, b: list) -> list:
    if len(a) < len(b):
        return []
    n = len(a) - len(b) + 1
    cnt = 0
    if len(b) > 64:
        return multiply(a[::-1][:n], fps_inv(b[::-1], n))[:n][::-1]
    f = a.copy()
    g = b.copy()
    while g and not g[-1]:
        g.pop()
        cnt += 1
    coef = pow(g[-1], MOD - 2, MOD)
    g = [x * coef % MOD for x in g]
    deg = len(f) - len(g) + 1
    lg = len(g)
    res = [0] * deg
    for i in reversed(range(deg)):
        res[i] = x = f[i + lg - 1] % MOD
        for j, y in enumerate(g):
            f[i + j] -= x * y
    return [x * coef % MOD for x in res] + [0] * cnt


def fps_mod(a: list, b: list) -> list:
    res = fps_sub(a, multiply(fps_div(a, b), b))
    while res and not res[-1]:
        res.pop()
    return res


def fps_divmod(a: list, b: list):
    q = fps_div(a, b)
    r = fps_sub(a, multiply(q, b))
    while r and not r[-1]:
        r.pop()
    return q, r


def fps_eval(a: list, x: int) -> int:
    r = 0
    w = 1
    for v in a:
        r += w * v % MOD
        w = w * x % MOD
    return r % MOD


def fps_inv(a: list, deg: int = -1):
    # assert(self[0] != 0)
    if deg == -1:
        deg = len(a)
    res = [0] * deg
    res[0] = pow(a[0], MOD - 2, MOD)
    d = 1
    iv = INV2
    while d < deg:
        d2 = d << 1
        f = [0] * d2
        fl = min(len(a), d2)
        f[:fl] = a[:fl]
        g = [0] * d2
        g[:d] = res[:d]
        butterfly(g)
        butterfly(f)
        for i in range(d2):
            f[i] = f[i] * g[i] % MOD
        butterfly_inv(f)
        f[:d] = [0] * d
        for i in range(d, d2):
            f[i] = f[i] * iv % MOD
        butterfly(f)
        for i in range(d2):
            f[i] = f[i] * g[i] % MOD
        butterfly_inv(f)
        for i in range(d, min(d2, deg)):
            res[i] = (MOD - f[i]) * iv % MOD
        d <<= 1
        iv = iv * INV2 % MOD
    return res


def fps_pow(a: list, k: int, deg=-1) -> list:
    n = len(a)
    if deg == -1:
        deg = n
    if k == 0:
        if not deg:
            return []
        res = [0] * deg
        res[0] = 1
        return res
    for i, x in enumerate(a):
        if x:
            iz = pow(x, MOD - 2, MOD)
            res = [x * iz % MOD for x in a[i:]]
            res = fps_log(res, deg)
            res = [x * k % MOD for x in res]
            res = fps_exp(res, deg)
            coef = pow(x, k, MOD)
            res = [0] * (i * k) + [x * coef % MOD for x in res]
            if len(res) < deg:
                return res + [0] * (deg - len(res))
            return res[:deg]
        if (i + 1) * k >= deg:
            break
    return [0] * deg


def fps_exp(a: list, deg: int = -1):
    # assert a[0] == 0
    if deg == -1:
        deg = len(a)
    inv = [0, 1]

    def inplace_integral(f: list) -> list:
        n = len(f)
        while len(inv) <= n:
            j, k = divmod(MOD, len(inv))
            inv.append((-inv[k] * j) % MOD)
        return [0] + [x * inv[i + 1] % MOD for i, x in enumerate(f)]

    b = [1, (a[1] if 1 < len(a) else 0)]
    c = [1]
    z1 = []
    z2 = [1, 1]
    m = 2
    while m < deg:
        y = b + [0] * m
        butterfly(y)
        z1 = z2
        z = [y[i] * p % MOD for i, p in enumerate(z1)]
        intt(z)
        z[: m >> 1] = [0] * (m >> 1)
        butterfly(z)
        for i, p in enumerate(z1):
            z[i] = z[i] * (-p) % MOD
        intt(z)
        c[m >> 1 :] = z[m >> 1 :]
        z2 = c + [0] * m
        butterfly(z2)
        tmp = min(len(a), m)
        x = a[:tmp] + [0] * (m - tmp)
        x = fps_diff(x)
        x.append(0)
        butterfly(x)
        for i, p in enumerate(x):
            x[i] = y[i] * p % MOD
        intt(x)
        for i, p in enumerate(b):
            if not i:
                continue
            x[i - 1] -= p * i % MOD
        x += [0] * m
        for i in range(m - 1):
            x[m + i], x[i] = x[i], 0
        butterfly(x)
        for i, p in enumerate(z2):
            x[i] = x[i] * p % MOD
        intt(x)
        x.pop()
        x = inplace_integral(x)
        x[:m] = [0] * m
        for i in range(m, min(len(a), m << 1)):
            x[i] += a[i]
        butterfly(x)
        for i, p in enumerate(y):
            x[i] = x[i] * p % MOD
        intt(x)
        b[m:] = x[m:]
        m <<= 1
    return b[:deg]


def fps_log(a: list, deg=-1) -> list:
    # assert(a[0] == 1)
    if deg == -1:
        deg = len(a)
    return fps_integral(multiply(fps_diff(a), fps_inv(a, deg))[: deg - 1])


def fps_integral(a: list):
    n = len(a)
    res = [0] * (n + 1)
    if n:
        res[1] = 1
    for i in range(2, n + 1):
        j, k = divmod(MOD, i)
        res[i] = (-res[k] * j) % MOD
    for i, x in enumerate(a):
        res[i + 1] = res[i + 1] * x % MOD
    return res


def fps_diff(a: list):
    return [i * x % MOD for i, x in enumerate(a) if i]


def LinearRecurrence(n: int, p: list, q: list):
    """
    [x^n]P(x)/Q(x)
    """
    # assert len(p) < len(q)
    shrink(q)
    while n:
        q2 = q[:]
        for i in range(1, len(q2), 2):
            q2[i] = (-q2[i]) % MOD
        s = multiply(p, q2)
        t = multiply(q, q2)
        for i in range(n & 1, len(s), 2):
            p[i >> 1] = s[i]
        for i in range(0, len(t), 2):
            q[i >> 1] = t[i]
        n >>= 1
    return p[0] * pow(q[0], -1, MOD) % MOD


def fps_compsite(f: list, g: list):
    """
    g(f(x)) mod x^(n+1)
    """

    # assert len(f) == len(g)
    def trans_multiply(s, t):
        n = len(s)
        m = len(t)
        l = 1 << (max(n, m) - 1).bit_length()
        a = s + [0] * (l - n)
        b = t + [0] * (l - m)
        a = [a[0]] + [a[l - i] for i in range(1, l)]
        butterfly(a)
        butterfly(b)
        iz = pow(l, MOD - 2, MOD)
        for i, x in enumerate(b):
            a[i] = a[i] * x % MOD * iz % MOD
        butterfly_inv(a)
        a = [a[0]] + [a[l - i] for i in range(1, l)]
        return a[: n - m + 1]

    n = len(f)
    l = 1 << (n - 1).bit_length()
    a = [MOD - x for x in f] + [0] * (2 * l - n)
    b = g + [0] * (l - n)

    def _inner(q, n, k):
        if n == 1:
            p = [0] * (2 * k)
            p[0::2] = b[::-1]
            return p
        siz = 2 * n * k
        r = [MOD - x if i & 1 else x for i, x in enumerate(q)]
        qq = multiply(q, r)
        qq.append(0)
        for i in range(0, siz, 2):
            qq[siz + i] = (qq[siz + i] + 2 * q[i]) % MOD
        nq = [0] * siz
        for j in range(2 * k):
            for i in range(n >> 1):
                nq[n * j + i] = qq[2 * n * j + 2 * i]
        np = _inner(nq, n >> 1, k << 1)

        pq = [0] * (2 * siz)
        for j in range(2 * k):
            for i in range(n >> 1):
                pq[2 * n * j + 2 * i + 1] = np[n * j + i]

        p = [pq[siz + i] for i in range(siz)]
        pq.pop()
        x = trans_multiply(pq, r)
        p = [(p[i] + x[i]) % MOD for i in range(siz)]
        return p

    p = _inner(a, l, 1)
    p = p[l - 1 :: -1]
    return p[:n]


def fps_compsitional_inv(calc, deg):
    """
    input
    calc(g, d) = f(g(x)) mod x^d を計算する
    fps_compsite よりも良い計算量のものが存在するならば書く

    output
    g(x) mod x^deg s.t. f(g(x)) = x
    """
    c = deg.bit_length()
    g = calc([0, 1], 2)
    g[1] = pow(g[1], -1, MOD)
    d = 2
    for i in range(c):
        d <<= 1
        fg = calc(g, d + 1)
        fdg = multiply(fps_diff(fg), fps_inv(fps_diff(g)))
        fdg[d:] = []
        fg[1] -= 1
        g = fps_sub(g, multiply(fg, fps_inv(fdg)))
        g[d:] = []
    g[deg:] = []
    return g


INVMOD = [1, 1]


def SubsetSum(d: list) -> list:
    """
    prod ( 1 + x^i ) ^ d[i]

    d[w] = 重さ w が d[w] 種類 1 個ずつある
    r[w] = 重さが w になるような選び方
    """
    n = len(d)
    for i in range(len(INVMOD), n):
        INVMOD.append(-INVMOD[MOD % i] * (MOD // i) % MOD)
    res = [0] * n
    sgn = [-1, 1]
    for i in range(1, n):
        if d[i]:
            tmp = d[i] * i
            for j in range(i, n, i):
                res[j] += tmp * INVMOD[j] * sgn[(j // i) & 1] % MOD
    res = fps_exp(res, n)
    return res


def MultisetSum(d: list) -> list:
    """
    prod ( 1 / ( 1 - x^i ) ) ^ d[i]

    d[w] = 重さ w が d[w] 種類 inf 個ずつある
    r[w] = 重さが w になるような選び方
    """
    n = len(d)
    for i in range(len(INVMOD), n):
        INVMOD.append(-INVMOD[MOD % i] * (MOD // i) % MOD)
    res = [0] * n
    for i in range(1, n):
        if d[i]:
            tmp = d[i] * i
            for j in range(i, n, i):
                res[j] += tmp * INVMOD[j] % MOD
    res = fps_exp(res, n)
    return res


fac = [1, 1]
finv = [1, 1]


def tayler_shift(a: list, c: int) -> list:
    global fac, finv
    n = len(a)
    l = len(fac)
    fac += [0] * (n - l)
    finv += [0] * (n - l)
    for i in range(l, n):
        fac[i] = fac[i - 1] * i % MOD
    finv[n - 1] = pow(fac[n - 1], MOD - 2, MOD)
    for i in reversed(range(l, n - 1)):
        finv[i] = finv[i + 1] * (i + 1) % MOD

    r = [x * fac[i] % MOD for i, x in enumerate(a)]
    b = [0] * n
    b[0] = 1
    for i in range(1, n):
        b[i] = b[i - 1] * c % MOD * finv[i] % MOD * fac[i - 1] % MOD
    r.reverse()
    res = multiply(r, b)[:n]
    return [x * finv[i] % MOD for i, x in enumerate(reversed(res))]


def _fft2d(s: list[list]):
    h, w = len(s), len(s[0])
    for i in range(h):
        butterfly(s[i])
    buf = [0] * h
    for j in range(w):
        buf = [s[i][j] for i in range(h)]
        butterfly(buf)
        for i in range(h):
            s[i][j] = buf[i]


def _ifft2d(s: list[list]):
    h, w = len(s), len(s[0])
    buf = [0] * h
    for j in range(w):
        buf = [s[i][j] for i in range(h)]
        intt(buf)
        for i in range(h):
            s[i][j] = buf[i]
    for i in range(h):
        intt(s[i])


def multiply_2D(s: list[list], t: list[list]):
    """
    not verify
    """
    from copy import deepcopy

    hs, ws = len(s), len(s[0])
    ht, wt = len(t), len(t[0])
    h = 1 << (hs + ht - 2).bit_length()
    w = 1 << (ws + wt - 2).bit_length()
    a = deepcopy(s)
    b = deepcopy(t)
    for i in range(hs):
        a[i] += [0] * (w - ws)
    for i in range(ht):
        b[i] += [0] * (w - wt)
    a += [[0] * w for i in range(h - hs)]
    b += [[0] * w for i in range(h - ht)]
    _fft2d(a)
    _fft2d(b)
    for i in range(h):
        for j in range(w):
            a[i][j] *= b[i][j]
            a[i][j] %= MOD
    _ifft2d(a)
    a = a[: hs + ht - 1]
    for i in range(hs + ht - 1):
        a[i][ws + wt - 1 :] = []
    return a

・Bostan-Mori法
# https://atcoder.jp/contests/tdpc/submissions/29624177
CONV = FFT(MOD)
def Bostan_Mori(P,Q,N):
    """
    [x^n] P(x)/Q(x) を d^2 log N ないし d log d log N で求める
    """
    if N==0:
        return P[0]
    Q2=[]
    for i in range(len(Q)):
        if i%2:Q2.append(-Q[i])
        else:Q2.append(Q[i])
    V=CONV.convolution(Q,Q2)[::2]
    if N%2:return Bostan_Mori(CONV.convolution(P,Q2)[1::2],V,N//2)
    else:return Bostan_Mori(CONV.convolution(P,Q2)[::2],V,N//2)

・階乗
def factorial(n):
    F = [1]
    for i in range(1, n+1):
        F.append(F[-1]*i%MOD)
    invF = [pow(F[-1], -1, MOD)]
    for i in reversed(range(n)):
        invF.append(invF[-1]*(i+1)%MOD)
    invF = invF[::-1]
    return F, invF

・グラフ ランダム生成
def gen_connected_graph(N, M, rng):
    assert M >= N-1
    edges = []
    used = set()

    # まず木を作る
    for i in range(1, N):
        p = rng.randint(0, i-1)
        u, v = min(p, i), max(p, i)
        edges.append((u, v))
        used.add((u, v))

    # 残りの辺をランダム追加
    while len(edges) < M:
        u = rng.randint(0, N-1)
        v = rng.randint(0, N-1)
        if u == v:
            continue
        u, v = min(u, v), max(u, v)
        if (u, v) in used:
            continue
        edges.append((u, v))
        used.add((u, v))

    return edges

・UnionFind（左右を管理）
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent_size = [-1]*n
        self.L = list(range(n))
        self.R = list(range(n))
 
    def leader(self, a):
        if self.parent_size[a] < 0:
            return a
        self.parent_size[a] = self.leader(self.parent_size[a])
        return self.parent_size[a]
 
    def merge(self, a, b):
        x, y = self.leader(a), self.leader(b)
        if x == y:
            return 
        if abs(self.parent_size[x]) < abs(self.parent_size[y]):
            x, y = y, x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y] = x
        self.L[x] = min(self.L[x], self.L[y])
        self.R[x] = max(self.R[x], self.R[y])
        return 
    
    def left(self, n):
        return self.L[self.leader(n)]
    
    def right(self, n):
        return self.R[self.leader(n)]
 
    def same(self, a, b):
        return self.leader(a) == self.leader(b)
 
    def size(self, a):
        return abs(self.parent_size[self.leader(a)])
 
    def groups(self):
        result = [[] for _ in range(self.n)]
        for i in range(self.n):
            result[self.leader(i)].append(i)
        return [r for r in result if r != []]

・行列式
def det(A):
    ans = 1
    N = len(A)
    sign = 1
    for i in range(N):
        pivot = i
        while pivot < N and A[pivot][i] == 0:
            pivot += 1
        if pivot == N:
            return 0
        
        if pivot != i:
            A[i], A[pivot] = A[pivot], A[i]
            sign *= -1
        
        inv = pow(A[i][i], -1, MOD)
        
        for j in range(i+1, N):
            factor = A[j][i]*inv%MOD
            for k in range(i, N):
                A[j][k] = (A[j][k]-factor*A[i][k])%MOD
        
        ans *= A[i][i]
        ans %= MOD
    
    ans *= sign
    ans %= MOD
    return ans

・最小共通祖先（重み付き）
class LCA:
    def __init__(self, G, root=0):
        V = len(G)
        self.bit_length = 1
        while 1<<self.bit_length < V:
            self.bit_length += 1
        self.parent = [[-1]*V for _ in range(self.bit_length)]
        self.depth = [-1]*V
        self.depth2 = [-1]*V
        self.bfs(G, root)
        for i in range(self.bit_length-1):
            for j in range(V):
                if self.parent[i][j] != -1:
                    self.parent[i+1][j] = self.parent[i][self.parent[i][j]]
        
    def bfs(self, G, root):
        self.depth[root] = 0
        que = deque()
        que.append(root)
        while que:
            n = que.popleft()
            for v, w in G[n]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[n]+1
                    self.depth2[v] = self.depth2[n]+w
                    self.parent[0][v] = n
                    que.append(v)
    
    def lca(self, a, b):
        if self.depth[a] < self.depth[b]:
            a, b = b, a
        for i in range(self.bit_length):
            if (self.depth[a]-self.depth[b]) & 1<<i:
                a = self.parent[i][a]
        if a == b:
            return a
        for i in reversed(range(self.bit_length)):
            if self.parent[i][a] != self.parent[i][b]:
                a = self.parent[i][a]
                b = self.parent[i][b]
        return self.parent[0][a]
    
    def dist(self, a, b):
        return self.depth[a]+self.depth[b]-self.depth[self.lca(a, b)]*2
    
    def dist2(self, a, b):
        return self.depth2[a]+self.depth2[b]-self.depth2[self.lca(a, b)]*2
    
    def is_ancestor(self, u, v):
        return self.lca(u, v) == u
    
    def kth_ancestor(self, n, k):
        for i in range(self.bit_length):
            if 1<<i & k:
                n = self.parent[i][n]
                if n == -1:
                    break
        return n
    
    def jump(self, u, v):
        if u == v:
            return u
        if self.lca(u, v) == u:
            return self.kth_ancestor(v, self.dist(u, v)-1)
        else:
            return self.parent[0][u]
    
    def jump_k(self, u, v, k):
        d = self.dist(u, v)
        if d <= k:
            return v
        lca = self.lca(u, v)
        if k <= self.depth[u]-self.depth[lca]:
            return self.kth_ancestor(u, k)
        else:
            return self.kth_ancestor(v, d-k)
    
    def on_path(self, u, v, x):
        return self.dist(u, x)+self.dist(x, v) == self.dist(u, v)

    def create_path(self, u, v, x):
        if self.on_path(u, v, x):
            return u, v
        if self.on_path(u, x, v):
            return u, x
        if self.on_path(v, x, u):
            return v, x
        return -1, -1

・（重み付き）AuxiliaryTree
class AuxiliaryTree:
    def __init__(self, N, G):
        self.N = N
        self.G = G
        self.IN = [0]*N
        self.OUT = [0]*N
        self.depth = [0]*N
        self.depth2 = [0]*N
        self.E = []
        self.dfs(0, -1, 0, 0)
        self.L = len(self.E)
        self.lg = [0]*(self.L+1)
        self.make_sparse_table()

    @bootstrap
    def dfs(self, n, p, d, d2):
        self.depth[n] = d
        self.depth2[n] = d2
        self.IN[n] = len(self.E)
        self.E.append(n)
        for v, w in self.G[n]:
            if v == p:
                continue
            yield self.dfs(v, n, d+1, d2+w)
            self.E.append(n)
        self.OUT[n] = len(self.E)
        self.E.append(n)
        yield
    
    def make_sparse_table(self):
        for i in range(2, self.L+1):
            self.lg[i] = self.lg[i>>1]+1
        self.st = [[self.L]*(self.L-(1<<i)+1) for i in range(self.lg[self.L]+1)]
        self.st[0] = self.E[:]
        b = 1
        for i in range(self.lg[self.L]):
            for j in range(self.L-(b<<1)+1):
                self.st[i+1][j] = (self.st[i][j] if self.depth[self.st[i][j]] <= self.depth[self.st[i][j+b]] else self.st[i][j+b])
            b <<= 1
    
    def lca(self, u, v):
        x, y = self.IN[u], self.IN[v]
        l = self.lg[y-x+1]
        return self.st[l][x] if self.depth[self.st[l][x]] <= self.depth[self.st[l][y-(1<<l)+1]] else self.st[l][y-(1<<l)+1]
    
    def query(self, v):
        nG = defaultdict(list)
        V = v[:]
        V.sort(key=self.IN.__getitem__)
        K = len(V)
        stack = [V[0]]
        for i in range(K-1):
            w = self.lca(V[i], V[i+1])
            if w != V[i]:
                last = stack.pop()
                while stack and self.depth[w] < self.depth[stack[-1]]:
                    d = abs(self.depth[stack[-1]]-self.depth[last])
                    d2 = abs(self.depth2[stack[-1]]-self.depth2[last])
                    nG[stack[-1]].append((last, d, d2))
                    nG[last].append((stack[-1], d, d2))
                    last = stack.pop()
                if not stack or stack[-1] != w:
                    stack.append(w)
                    V.append(w)
                d = abs(self.depth[w]-self.depth[last])
                d2 = abs(self.depth2[w]-self.depth2[last])
                nG[w].append((last, d, d2))
                nG[last].append((w, d, d2))
            stack.append(V[i+1])
        for i in range(len(stack)-1):
            d = abs(self.depth[stack[i]]-self.depth[stack[i+1]])
            d2 = abs(self.depth2[stack[i]]-self.depth2[stack[i+1]])
            nG[stack[i]].append((stack[i+1], d, d2))
            nG[stack[i+1]].append((stack[i], d, d2))
        return nG, stack[0]

・Aho-Corasick
class AhoCorasick:
    def __init__(self, type):
        self.next = [[-1]*26]
        self.link = [-1]
        self.out = [[]]
        self.size = 1
        self.base = ord("a") if type == 0 else ord("A")
    
    def code(self, s):
        return ord(s)-self.base

    def add_word(self, word, idx):
        v = 0
        for c in word:
            if self.next[v][self.code(c)] == -1:
                self.next[v][self.code(c)] = self.size
                self.next.append([-1]*26)
                self.link.append(0)
                self.out.append([])
                self.size += 1
            v = self.next[v][self.code(c)]
        self.out[v].append(idx)

    def build(self):
        que = deque()
        for i in range(26):
            if self.next[0][i] != -1:
                self.link[self.next[0][i]] = 0
                que.append(self.next[0][i])
        while que:
            n = que.popleft()
            for i in range(26):
                if self.next[n][i] != -1:
                    f = self.link[n]
                    while f != -1 and self.next[f][i] == -1:
                        f = self.link[f]
                    if f == -1:
                        self.link[self.next[n][i]] = 0
                    else:
                        self.link[self.next[n][i]] = self.next[f][i]
                    self.out[self.next[n][i]].extend(self.out[self.link[self.next[n][i]]])
                    que.append(self.next[n][i])

    def match(self, text):
        res = []
        n = 0
        for i, c in enumerate(text):
            while n != 0 and self.next[n][self.code(c)] == -1:
                n = self.link[n]
            if self.next[n][self.code(c)] != -1:
                n = self.next[n][self.code(c)]
            for idx in self.out[n]:
                res.append((i, idx))
        return res
    
    def go(self, idx, s):
        while 1 <= idx and self.next[idx][self.code(s)] == -1:
            idx = self.link[idx]
        return self.next[idx][self.code(s)] if self.next[idx][self.code(s)] != -1 else 0

・BIT（MOD）
class BIT:
    def __init__(self, A):
        self.size = len(A)
        self.bit = [0]*(len(A)+1)
        for i in range(len(A)):
            self.add(i, A[i])

    def sum(self, i):
        i += 1
        ans = 0
        while i > 0:
            ans += self.bit[i]
            ans %= MOD
            i -= -i&i
        return ans
    
    def query(self, l, r):
        if l == 0:
            return self.sum(r-1)
        else:
            return (self.sum(r-1)-self.sum(l-1))%MOD
    
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.bit[i] += x
            self.bit[i] %= MOD
            i += -i&i

・オフラインrangefreq
def offline_range_freq_to(A, query):
    N = len(A)
    Q = len(query)

    A = sorted(enumerate(A), key=lambda x:x[1])
    query = sorted(enumerate(query), key=lambda x:x[1][2])

    F = BIT([0]*N)
    ans = [-1]*Q
    idx = 0
    for qidx, (l, r, x) in query:
        while idx < N and A[idx][1] <= x:
            F.add(A[idx][0], 1)
            idx += 1
        ans[qidx] = F.query(l, r+1)
    return ans

def offline_range_freq_from(A, query):
    N = len(A)
    Q = len(query)

    A = sorted(enumerate(A), key=lambda x:x[1], reverse=True)
    query = sorted(enumerate(query), key=lambda x:x[1][2], reverse=True)

    F = BIT([0]*N)
    ans = [-1]*Q
    idx = 0
    for qidx, (l, r, x) in query:
        while idx < N and x <= A[idx][1]:
            F.add(A[idx][0], 1)
            idx += 1
        ans[qidx] = F.query(l, r+1)
    return ans

・Codonテンプレート
#generatorに__getitem__, __contains__を定義
@extend
class Generator:
    def __getitem__(self: Generator[T], _: int) -> T:
        if self.done(): raise StopIteration()
        return self.next()
    def __getitem__(self: Generator[T], key: slice) -> list[T]:
        assert key.stop is None, (
            '''本拡張では、末尾以外でのアンパッキングはできません。
            例として、 N, *A = generator には対応しますが *A, N = generator は非対応です。
            右辺の generator を list(generator) と書き換えてみてください。''')
        return list(self)
    def __contains__(self: Generator[T], key: T) -> bool:
        return key in list(self)

#int同士の除算結果をPythonの負の無限大丸めに合わせる
@extend
class int:
    @pure
    @llvm
    def _floordiv_int_int(self: int, other: int) -> int:
        %0 = sdiv i64 %self, %other
        ret i64 %0
    @overload
    def __floordiv__(self, other: int):
        d = self._floordiv_int_int(other)
        m = self - d * other
        if m and ((other ^ m) < 0):
            d -= 1
        return d
    @pure
    @llvm
    def _mod_int_int(self: int, other: int) -> int:
        %0 = srem i64 %self, %other
        ret i64 %0
    @overload
    def __mod__(self, other: int) -> int:
        m = self._mod_int_int(other)
        if m and ((other ^ m) < 0):
            m += other
        return m

#int.bit_length, int.bit_countに対応
@extend
class int:
    def bit_length(self): 
        return 64 - abs(self).__ctlz__()
    def bit_count(self):
        return abs(self).__ctpop__()

#int hash値をSplitMix64で変更する
#Reference: https://prng.di.unimi.it/splitmix64.c
@extend
class int:
    def __hash__(self) -> int:
        z: UInt[64] = UInt[64](self) + UInt[64](0x9e3779b97f4a7c15)
        z = (z ^ (z >> UInt[64](30))) * UInt[64](0xbf58476d1ce4e5b9)
        z = (z ^ (z >> UInt[64](27))) * UInt[64](0x94d049bb133111eb)
        return int(z ^ (z >> UInt[64](31)))

#floatの出力桁数を15桁に増やす
@extend
class float:
    def __str__(self): return f'{self:15f}'

#巨大mod時のオーバーフローを回避  pow(base, -1, mod)に対応
def _extended_pow():
    _builtin_pow = pow
    def _codon_pow(base, exp):
        return _builtin_pow(base, exp)
    @overload
    def _codon_pow(base: int, exp: int, mod: int) -> int:
        '''
        codon用に pow(base, exp, mod) を拡張した関数です。
        1. (abs(mod) - 1) ** 2 >= 1 << 63 の場合に発生していたオーバーフローを回避しました。
        2. pow(base: int, exp: 負整数, mod: int) による逆元計算に対応しました。

        返り値の符号は mod の符号に一致します。
        いずれかの引数に INF_MIN := -1 << 63 を渡した場合の動作は未定義です。
        '''
        if mod == 0:
            raise ValueError('pow() 3rd argument cannot be 0')
        if mod == 1 or mod == -1:
            return 0
        if exp < 0:  #拡張ユークリッドの互除法
            a, b, x, y = base, mod, 1, 0
            while b:
                q = a // b
                a, b, x, y = b, a - q * b, y, x - q * y
            if a != 1 and a != -1:
                raise ValueError('base is not invertible for the given modulus')
            b128, m128 = Int[128](x), Int[128](mod)
            if a == -1:
                b128 = - b128
            exp = - exp
        else:
            b128, m128 = Int[128](base), Int[128](mod)
        v128 = Int[128](1)
        while exp:
            if exp & 1 == 1:
                v128 = v128 * b128 % m128
            b128 = b128 * b128 % m128
            exp >>= 1
        v = int(v128)
        return v + mod if v != 0 and (0 < v) != (0 < mod) else v
    return _codon_pow
pow = _extended_pow()

・スライド最小値（最大値）
class MonotonicQueue:
    def __init__(self, A, isMIN=True):
        self.N = len(A)
        self.A = A
        self.isMIN = isMIN
        self.que = deque()
        self.left = 0
        self.right = 0
    
    def _cmp(self, a, b):
        return a >= b if self.isMIN else a <= b
    
    def move_right(self):
        if self.right == self.N: return False
        while self.que and self._cmp(self.que[-1][0], self.A[self.right]):
            self.que.pop()
        self.que.append((self.A[self.right], self.right))
        self.right += 1
        return True

    def move_left(self):
        if self.left == self.right: return False
        if self.que[0][1] == self.left:
            self.que.popleft()
        self.left += 1
        return True
    
    def get(self):
        return self.que[0][0] if self.que else None

・オイラーグラフ判定
def isEulerGraph(G, isDirected = False):
    N = len(G)
    if not isDirected:
        cnt = [0]*N
        UF = UnionFind(N)
        for n in range(N):
            for v in G[n]:
                cnt[n] += 1
                UF.merge(n, v)
        odd = sum(cnt[i]%2 == 1 for i in range(N))
        cntE = sum(1 <= cnt[i] for i in range(N))
        if odd == 0:
            if 1 <= cntE:
                for i in range(N):
                    if 1 <= cnt[i]:
                        if UF.size(i) == cntE:
                            return True, True, i, -1
                        else:
                            return False, False, -1, -1
            else:
                return True, True, -1, -1
        elif odd == 2:
            l, r = -1, -1
            for i in range(N):
                if cnt[i]%2 == 1:
                    if l == -1:
                        l = i
                    else:
                        r = i
                        break
            if UF.size(l) == cntE:
                return True, False, l, r
            else:
                return False, False, -1, -1
        else:
            return False, False, -1, -1
    else:
        IN = [0]*N
        OUT = [0]*N
        UF = UnionFind(N)
        for n in range(N):
            for v in G[n]:
                OUT[n] += 1
                IN[v] += 1
                UF.merge(n, v)
        s, g = -1, -1
        m = -1
        cntE = sum(1 <= IN[i]+OUT[i] for i in range(N))
        for i in range(N):
            if IN[i]+1 == OUT[i]:
                if s == -1:
                    s = i
                else:
                    return False, False, -1, -1
            elif OUT[i]+1 == IN[i]:
                if g == -1:
                    g = i
                else:
                    return False, False, -1, -1
            elif IN[i] != OUT[i]:
                return False, False, -1, -1
            if 1 <= IN[i]+OUT[i] and m == -1:
                m = i
        if m != -1 and UF.size(m) != cntE:
            return False, False, -1, -1
        if s == g == -1:
            return True, True, m, -1
        elif s != -1 and g != -1:
            return True, False, s, g
        else:
            return False, False, -1, -1

・二項係数の区間和
class rangeBinomial:
    def __init__(self, N, L, R):
        self.N = N
        self.L = L
        self.R = R
        self.val = 0
        for i in range(L, R+1):
            self.val += cp.C(N, i)
            self.val %= MOD
        self.half = pow(2, -1, MOD)
    
    def add(self):
        self.val *= 2
        self.val %= MOD
        self.val += cp.C(self.N, self.L-1)-cp.C(self.N, self.R)
        self.val %= MOD
        self.N += 1
        return True

    def sub(self):
        if self.N == 0:
            return False
        self.N -= 1
        self.val += cp.C(self.N, self.R)-cp.C(self.N, self.L-1)
        self.val %= MOD
        self.val *= self.half
        self.val %= MOD
        return True
    
    def move_ll(self):
        if self.L == 0:
            return False
        self.L -= 1
        self.val += cp.C(self.N, self.L)
        self.val %= MOD
        return True
    
    def move_lr(self):
        if self.L == self.R:
            return False
        self.val -= cp.C(self.N, self.L)
        self.val %= MOD
        self.L += 1
        return True
    
    def move_rr(self):
        self.R += 1
        self.val += cp.C(self.N, self.R)
        self.val %= MOD
        return True
    
    def move_rl(self):
        if self.L == self.R:
            return False
        self.val -= cp.C(self.N, self.R)
        self.val %= MOD
        self.R -= 1
        return True

    def get(self):
        return self.val

・円の交点
def circle_intersections(x1, y1, r1, x2, y2, r2):
    d = distance(x1, y1, x2, y2)
    dx = x2 - x1
    dy = y2 - y1

    # 交点なし
    if d > r1 + r2 or d < abs(r1 - r2) or d == 0:
        return []

    a = (r1*r1 - r2*r2 + d*d) / (2*d)
    h_sq = r1*r1 - a*a
    if h_sq < 0:
        h_sq = 0
    h = h_sq**0.5

    x3 = x1 + a * dx / d
    y3 = y1 + a * dy / d

    rx = -dy * (h / d)
    ry = dx * (h / d)

    return [(x3 + rx, y3 + ry), (x3 - rx, y3 - ry)]

・2-SAT
class TwoSAT:
    def __init__(self, N):
        self.N = N
        self.edge = []
        self.solution = [False]*N
        self.solved = False
    
    def add_constraint(self, u, f, v, g):
        self.edge.append((u+self.N*f, v+self.N*g))

    def add_clause(self, u, f, v, g):
        self.add_constraint(u, f^True, v, g)
        self.add_constraint(v, g^True, u, f)
    
    def solve(self):
        SCC = scc(self.N*2, self.edge)
        order = [-1]*(self.N*2)
        for i, s in enumerate(SCC):
            for n in s:
                order[n] = i
        for i in range(self.N):
            if order[i] == order[i+self.N]:
                return False
            if order[i] > order[i+self.N]:
                self.solution[i] = False
            else:
                self.solution[i] = True
        self.solved = True
        return True
    
    def result(self):
        return self.solution if self.solved else None

・2-SAT（密グラフ）
class TwoSAT:
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.edge = []
        self.solution = [False]*self.N
        self.cnt = 0
        self.solved = False
    
    def add_constraint(self, u, f, v, g):
        self.edge.append((u+(self.N+self.M)*f, v+(self.N+self.M)*g))

    def add_clause(self, u, f, v, g):
        self.add_constraint(u, f^True, v, g)
        self.add_constraint(v, g^True, u, f)
    
    def add_at_most_one(self, A):
        for i in range(len(A)):
            self.add_clause(A[i][0], A[i][1], self.N+self.cnt+i, True)
            if i+1 < len(A):
                self.add_clause(self.N+self.cnt+i, False, self.N+self.cnt+i+1, True)
                self.add_clause(self.N+self.cnt+i, False, A[i+1][0], A[i+1][1])
        self.cnt += len(A)
    
    def solve(self):
        SCC = scc((self.N+self.M)*2, self.edge)
        order = [-1]*((self.N+self.M)*2)
        for i, s in enumerate(SCC):
            for n in s:
                order[n] = i
        for i in range(self.N):
            if order[i] == order[i+self.N+self.M]:
                return False
            if order[i] > order[i+self.N+self.M]:
                self.solution[i] = False
            else:
                self.solution[i] = True
        self.solved = True
        return True
    
    def result(self):
        return self.solution[:self.N] if self.solved else None

・Slope-Trick
from heapq import heappush, heappop

class SlopeTrick:
    def __init__(self):
        self.min_f = 0
        self.L = []
        self.R = []
        self.add_l = 0
        self.add_r = 0
    
    def push_R(self, a):
        heappush(self.R, a-self.add_r)
    
    def top_R(self):
        return self.R[0]+self.add_r if self.R else INF
    
    def pop_R(self):
        val = self.top_R()
        if self.R: heappop(self.R)
        return val
    
    def push_L(self, a):
        heappush(self.L, -(a-self.add_l))
    
    def top_L(self):
        return -self.L[0]+self.add_l if self.L else -INF
    
    def pop_L(self):
        val = self.top_L()
        if self.L: heappop(self.L)
        return val
    
    def size(self):
        return len(self.L)+len(self.R)
    
    def query(self):
        return self.top_L(), self.top_R(), self.min_f
    
    def add_all(self, a):
        self.min_f += a
    
    def add_x_minus_a(self, a):
        self.min_f += max(self.top_L()-a, 0)
        self.push_L(a)
        self.push_R(self.pop_L())

    def add_a_minus_x(self, a):
        self.min_f += max(a-self.top_R(), 0)
        self.push_R(a)
        self.push_L(self.pop_R())
    
    def add_abs(self, a):
        self.add_x_minus_a(a)
        self.add_a_minus_x(a)
    
    def clear_right(self):
        self.R = []

    def clear_left(self):
        self.L = []
    
    def shift2(self, a, b):
        self.add_l += a
        self.add_r += b
    
    def shift(self, a):
        self.shift2(a, a)
    
    def get(self, x):
        ret = self.min_f
        for l in self.L:
            n = -l+self.add_l
            ret += max(n-x, 0)
        for r in self.R:
            n = r+self.add_r
            ret += max(x-n, 0)
        return ret
    
    def merge(self, st):
        if self.size() < st.size():
            self.L, st.L = st.L, self.L
            self.R, st.R = st.R, self.R
            self.add_l, st.add_l = st.add_l, self.add_l
            self.add_r, st.add_r = st.add_r, self.add_r
            self.min_f, st.min_f = st.min_f, self.min_f
        while st.R:
            self.add_x_minus_a(st.pop_R())
        while st.L:
            self.add_a_minus_x(st.pop_L())
        self.min_f += st.min_f

・monotone minima
# select(i, j, k) AijとAikでAikを選ぶならTrue
def monotone_minima(H, W, select):
    def solve(row):
        L = len(row)
        if L == 0: return []
        row2 = [row[i] for i in range(L) if i%2 == 1]
        ans2 = solve(row2)
        ans = [0]*L
        for i in range(len(ans2)):
            ans[i*2+1] = ans2[i]
        idx = 0
        for i in range(0, L, 2):
            ans[i] = idx
            end = ans[i+1] if i+1 < L else W-1
            while idx != end:
                idx += 1
                if select(row[i], ans[i], idx): ans[i] = idx
        return ans
    return solve(list(range(H)))

・最大値（最小値）Top2
class Top2:
    def __init__(self):
        self.best1 = (-INF, -1)
        self.best2 = (-INF, -1)

    def add(self, val, genre):
        b1v, b1g = self.best1
        b2v, b2g = self.best2

        if genre == b1g:
            if val > b1v:
                self.best1 = (val, genre)
        else:
            if val > b1v:
                self.best2 = self.best1
                self.best1 = (val, genre)
            elif val > b2v:
                self.best2 = (val, genre)

    def get_exclude(self, genre):
        if self.best1[1] != genre:
            return self.best1[0]
        else:
            return self.best2[0]

・LCA（Sparse Table）
class LCA:
    def __init__(self, G, root=0):
        self.G = G
        self.N = len(G)
        self.A = []
        self.IN = [0]*self.N
        self.depth = [0]*self.N
        self.dfs(root, -1, 0)

        self.L = len(self.A)
        self.log = [0]*(self.L + 1)
        for i in range(2, self.L+1):
            self.log[i] = self.log[i >> 1] + 1
        self.sparse = [None]*(self.log[self.L] + 1)
        self.sparse[0] = self.A
        b = 1
        for i in range(self.log[self.L]):
            self.sparse[i+1] = [p if self.depth[p] <= self.depth[q] else q for p, q in zip(self.sparse[i], self.sparse[i][b:])]
            b <<= 1

    @bootstrap
    def dfs(self, n, p, d):
        self.depth[n] = d
        self.IN[n] = len(self.A)
        self.A.append(n)
        for v in self.G[n]:
            if v == p:
                continue
            yield self.dfs(v, n, d+1)
            self.A.append(n)
        yield
    
    def lca(self, u, v):
        l = self.IN[u]
        r = self.IN[v]
        if l > r:
            l, r = r, l
        k = self.log[r-l+1]
        a = self.sparse[k][l]
        b = self.sparse[k][r-(1<<k)+1]
        return a if self.depth[a] <= self.depth[b] else b
    
    def dist(self, a, b):
        return self.depth[a]+self.depth[b]-self.depth[self.lca(a, b)]*2

・XOR基底
class XORBasis:
    def __init__(self, A):
        self.A = A
        self.base = []
        self.mask = []
        self.IDX = []
        self.dependent = -1
        for i, a in enumerate(self.A):
            n = a
            xor = 1<<len(self.base)
            for j, b in enumerate(self.base):
                if n^b < n:
                    n ^= b
                    xor ^= self.mask[j]
            if n:
                self.IDX.append(i)
                self.base.append(n)
                self.mask.append(xor)
            elif self.dependent == -1:
                self.dependent = i
        if len(self.base) == 0:
            return
        pairs = sorted(zip(self.base, self.mask), key=lambda x:x[0], reverse=True)
        self.base, self.mask = map(list, zip(*pairs))
        for i in range(1, len(self.base)):
            for j in range(i):
                if self.base[j]^self.base[i] < self.base[j]:
                    self.base[j] ^= self.base[i]
                    self.mask[j] ^= self.mask[i]

    def can_make(self, x):
        for b in self.base:
            if 1<<(b.bit_length()-1) & x:
                x ^= b
        return x == 0

    def can_make_nonemptyzero(self):
        return self.dependent != -1

    def get_indices(self, x):
        xor = 0
        for i, b in enumerate(self.base):
            if 1<<(b.bit_length()-1) & x:
                x ^= b
                xor ^= self.mask[i]
        if x:
            return None
        ans = []
        for i in range(len(self.base)):
            if 1<<i & xor:
                ans.append(self.IDX[i])
        return ans

    def get_indices_nonemptyzero(self):
        if not self.can_make_nonemptyzero():
            return None
        return sorted(self.get_indices(self.A[self.dependent])+[self.dependent])

    def get_max(self, x = 0):
        for b in self.base:
            x = max(x, x^b)
        return x

    def get_min(self, x = 0):
        for b in self.base:
            x = min(x, x^b)
        return x

    def kth_min(self, k):
        if k < 0 or 1<<len(self.base) < k:
            return -1
        ans = 0
        for i, b in enumerate(self.base):
            if 1<<(len(self.base)-1-i) & k:
                ans ^= b
        return ans

    def kth_max(self, k):
        return self.kth_min((1<<len(self.base))-k)

・XOR畳み込み
def FWHT(A, inverse=False):
    N = len(A)

    H = 1
    while H < N:
        for i in range(0, N, H*2):
            for j in range(i, i+H):
                x = A[j]
                y = A[j+H]
                A[j] = (x+y)%MOD
                A[j+H] = (x-y)%MOD
        H *= 2

    if inverse:
        inv = pow(N, -1, MOD)
        for i in range(N):
            A[i] *= inv
            A[i] %= MOD

def xor_convolution(a, b):
    A = a[:]
    B = b[:]
    
    N = 1
    while N < max(len(A), len(B)):
        N *= 2
    A += [0]*(N-len(A))
    B += [0]*(N-len(B))

    FWHT(A)
    FWHT(B)

    for i in range(N):
        A[i] *= B[i]
        A[i] %= MOD

    FWHT(A, inverse=True)

    return A

・ランダムテスト
import subprocess
import sys
from random import randrange, shuffle

# 1.ファイル名を書き換える
SOL = ".py"
NAIVE = "_naive.py"
TEST_COUNT = 100
TIMEOUT_SECOND = 2

def generate():
    # 2.入力を作成する
    lines = []

    return "\n".join(lines)+"\n"

def prepare(filename):
    """
    実行するコマンドを返す。
    Pythonならそのまま。
    C++なら先にコンパイルする。
    """

    if filename.endswith(".py"):
        return [sys.executable, filename]

    if filename.endswith(".cpp"):
        exe = filename[:-4] + ".exe"

        result = subprocess.run(
            [
                "g++",
                filename,
                "-std=c++20",
                "-O2",
                "-o",
                exe,
            ],
            text=True,
            capture_output=True,
        )

        if result.returncode != 0:
            print(f"{filename} のコンパイルに失敗")
            print(result.stderr)
            exit()

        return [exe]

    raise ValueError(f"対応していないファイル形式: {filename}")

def run(command, test):
    try:
        result = subprocess.run(
            command,
            input=test,
            text=True,
            capture_output=True,
            timeout=TIMEOUT_SECOND,
        )
    except subprocess.TimeoutExpired:
        print("TLE!")
        print("command:", command)
        print("===== input =====")
        print(test, end="")
        exit()

    if result.returncode != 0:
        print("RE!")
        print("command:", command)
        print("===== input =====")
        print(test, end="")
        print("===== stderr =====")
        print(result.stderr)
        exit()

    return result.stdout.strip()

sol_command = prepare(SOL)
naive_command = prepare(NAIVE)

for t in range(TEST_COUNT):
    test = generate()

    ans1 = run(sol_command, test)
    ans2 = run(naive_command, test)

    if ans1 != ans2:
        print("WA")
        print("===== input =====")
        print(test, end="")
        print("===== solution =====")
        print(ans1)
        print("===== naive =====")
        print(ans2)

        with open("failed.txt", "w") as f:
            f.write(test)

        break
else:
    print("All tests passed!")

・ランダムテスト（小数誤差許容）
import subprocess
import sys
import math
from random import randrange, shuffle

# 1.ファイル名を書き換える
SOL = ".py"
NAIVE = "_naive.py"
TEST_COUNT = 100
TIMEOUT_SECOND = 2

# 2.許容誤差を設定する
ABS_EPS = 1e-6
REL_EPS = 1e-6

def generate():
    # 3.入力を作成する
    lines = []

    return "\n".join(lines)+"\n"

def prepare(filename):
    """
    実行するコマンドを返す。
    Pythonならそのまま。
    C++なら先にコンパイルする。
    """

    if filename.endswith(".py"):
        return [sys.executable, filename]

    if filename.endswith(".cpp"):
        exe = filename[:-4] + ".exe"

        result = subprocess.run(
            [
                "g++",
                filename,
                "-std=c++20",
                "-O2",
                "-o",
                exe,
            ],
            text=True,
            capture_output=True,
        )

        if result.returncode != 0:
            print(f"{filename} のコンパイルに失敗")
            print(result.stderr)
            exit()

        return [exe]

    raise ValueError(f"対応していないファイル形式: {filename}")

def run(command, test):
    try:
        result = subprocess.run(
            command,
            input=test,
            text=True,
            capture_output=True,
            timeout=TIMEOUT_SECOND,
        )
    except subprocess.TimeoutExpired:
        print("TLE!")
        print("command:", command)
        print("===== input =====")
        print(test, end="")
        exit()

    if result.returncode != 0:
        print("RE!")
        print("command:", command)
        print("===== input =====")
        print(test, end="")
        print("===== stderr =====")
        print(result.stderr)
        exit()

    return result.stdout.strip()

def compare(ans1, ans2):
    """
    空白区切りで比較する。

    数値なら誤差を許容。
    数値でないトークンは完全一致。
    """

    A = ans1.split()
    B = ans2.split()

    if len(A) != len(B):
        return False, f"出力トークン数が違う: {len(A)} != {len(B)}"

    for i, (a, b) in enumerate(zip(A, B)):
        try:
            x = float(a)
            y = float(b)

            if not math.isfinite(x) or not math.isfinite(y):
                return False, f"{i} 番目に非有限値がある: {a}, {b}"

            if not math.isclose(
                x,
                y,
                rel_tol=REL_EPS,
                abs_tol=ABS_EPS,
            ):
                return False, (
                    f"{i} 番目が誤差範囲外: "
                    f"{a} != {b}, diff = {abs(x-y)}"
                )

        except ValueError:
            # 数値でなければ文字列として比較
            if a != b:
                return False, f"{i} 番目が違う: {a} != {b}"

    return True, ""

sol_command = prepare(SOL)
naive_command = prepare(NAIVE)

for t in range(TEST_COUNT):
    test = generate()

    ans1 = run(sol_command, test)
    ans2 = run(naive_command, test)

    ok, reason = compare(ans1, ans2)

    if not ok:
        print("WA")
        print("===== input =====")
        print(test, end="")
        print("===== solution =====")
        print(ans1)
        print("===== naive =====")
        print(ans2)
        print("===== reason =====")
        print(reason)

        with open("failed.txt", "w") as f:
            f.write(test)

        break
else:
    print("All tests passed!")

・ランダムテスト（スペシャルジャッジ）
import subprocess
import sys
from random import randrange, shuffle

# 1.ファイル名を書き換える
SOL = ".py"
TEST_COUNT = 100
TIMEOUT_SECOND = 2

def generate():
    # 2.入力を作成する
    lines = []

    return "\n".join(lines)+"\n"

# 3.解答が正しいか判定するコードを書く
def check(test, output):
    """
    test   : generate() で作った入力
    output : SOL が出力した内容

    正しければ
        return True, ""
    間違っていれば
        return False, "間違っている理由"
    """
    test = test.splitlines()
    output = output.splitlines()

    return True, ""

def prepare(filename):
    """
    実行するコマンドを返す。
    Pythonならそのまま。
    C++なら先にコンパイルする。
    """

    if filename.endswith(".py"):
        return [sys.executable, filename]

    if filename.endswith(".cpp"):
        exe = filename[:-4] + ".exe"

        result = subprocess.run(
            [
                "g++",
                filename,
                "-std=c++20",
                "-O2",
                "-o",
                exe,
            ],
            text=True,
            capture_output=True,
        )

        if result.returncode != 0:
            print(f"{filename} のコンパイルに失敗")
            print(result.stderr)
            exit()

        return [exe]

    raise ValueError(f"対応していないファイル形式: {filename}")

def run(command, test):
    try:
        result = subprocess.run(
            command,
            input=test,
            text=True,
            capture_output=True,
            timeout=TIMEOUT_SECOND,
        )
    except subprocess.TimeoutExpired:
        print("TLE!")
        print("command:", command)
        print("===== input =====")
        print(test, end="")
        exit()

    if result.returncode != 0:
        print("RE!")
        print("command:", command)
        print("===== input =====")
        print(test, end="")
        print("===== stderr =====")
        print(result.stderr)
        exit()

    return result.stdout.strip()

sol_command = prepare(SOL)

for t in range(TEST_COUNT):
    test = generate()

    ans = run(sol_command, test)

    try:
        ok, reason = check(test, ans)
    except Exception as e:
        print("Checker Error!")
        print("===== input =====")
        print(test, end="")
        print("===== output =====")
        print(ans)
        print("===== checker error =====")
        print(repr(e))
        break

    if not ok:
        print("WA")
        print("===== input =====")
        print(test, end="")
        print("===== solution =====")
        print(ans)
        print("===== reason =====")
        print(reason)

        with open("failed.txt", "w") as f:
            f.write(test)

        break
else:
    print("All tests passed!")

・ランダムテスト（インタラクティブ）
import subprocess
import sys
import threading
import queue
from random import randrange, shuffle

# 1.ファイル名を書き換える
SOL = ".py"
TEST_COUNT = 100
TIMEOUT_SECOND = 2

# 2.ジャッジが持つ秘密の情報を生成する。
def generate():
    """
    普通のランテスと違って、
    必ずしも文字列を返す必要はない。

    例:
        N = randrange(1, 101)
        X = randrange(1, N+1)
        return N, X
    """

    return None

# 3.インタラクティブジャッジを書く。
def judge(io, case):
    """
    io.send(s)
        解答側に1行送る

    io.recv()
        解答側から1行受け取る

    正解:
        return True, ""

    不正解:
        return False, "理由"
    """

    # ==========================================
    # 例:
    #
    # N, X = case
    #
    # 最初にNを通知
    # io.send(str(N))
    #
    # query_count = 0
    #
    # while True:
    #     line = io.recv()
    #     tokens = line.split()
    #
    #     if len(tokens) == 2 and tokens[0] == "?":
    #         query_count += 1
    #
    #         if query_count > 20:
    #             return False, "質問回数オーバー"
    #
    #         x = int(tokens[1])
    #
    #         if not (1 <= x <= N):
    #             return False, "質問が範囲外"
    #
    #         if X <= x:
    #             io.send("Yes")
    #         else:
    #             io.send("No")
    #
    #     elif len(tokens) == 2 and tokens[0] == "!":
    #         answer = int(tokens[1])
    #
    #         if answer == X:
    #             return True, ""
    #         else:
    #             return False, f"答えが違う: {answer} != {X}"
    #
    #     else:
    #         return False, f"不正な出力: {line}"
    # ==========================================

    return True, ""


def prepare(filename):
    """
    実行するコマンドを返す。
    Pythonならそのまま。
    C++なら先にコンパイルする。
    """

    if filename.endswith(".py"):
        return [sys.executable, filename]

    if filename.endswith(".cpp"):
        exe = filename[:-4] + ".exe"

        result = subprocess.run(
            [
                "g++",
                filename,
                "-std=c++20",
                "-O2",
                "-o",
                exe,
            ],
            text=True,
            capture_output=True,
        )

        if result.returncode != 0:
            print(f"{filename} のコンパイルに失敗")
            print(result.stderr)
            exit()

        return [exe]

    raise ValueError(f"対応していないファイル形式: {filename}")


class InteractiveProcess:
    def __init__(self, command):
        self.proc = subprocess.Popen(
            command,
            stdin=subprocess.PIPE,
            stdout=subprocess.PIPE,
            stderr=subprocess.PIPE,
            text=True,
            bufsize=1,
        )

        self.stdout_queue = queue.Queue()
        self.stderr_lines = []
        self.transcript = []

        self.stdout_thread = threading.Thread(
            target=self._read_stdout,
            daemon=True,
        )
        self.stdout_thread.start()

        self.stderr_thread = threading.Thread(
            target=self._read_stderr,
            daemon=True,
        )
        self.stderr_thread.start()

    def _read_stdout(self):
        for line in self.proc.stdout:
            self.stdout_queue.put(line.rstrip("\r\n"))

        # EOF
        self.stdout_queue.put(None)

    def _read_stderr(self):
        for line in self.proc.stderr:
            self.stderr_lines.append(line)

    def send(self, s):
        """
        ジャッジ → 解答
        """

        if self.proc.poll() is not None:
            raise RuntimeError(
                f"解答プログラムが途中で終了した "
                f"(returncode={self.proc.returncode})"
            )

        s = str(s)

        self.transcript.append(("Judge", s))

        try:
            self.proc.stdin.write(s + "\n")
            self.proc.stdin.flush()
        except BrokenPipeError:
            raise RuntimeError("解答プログラムが入力を受け取る前に終了した")

    def recv(self):
        """
        解答 → ジャッジ
        """

        try:
            line = self.stdout_queue.get(
                timeout=TIMEOUT_SECOND
            )
        except queue.Empty:
            raise TimeoutError(
                f"{TIMEOUT_SECOND} 秒以内に応答がなかった"
            )

        if line is None:
            returncode = self.proc.poll()

            raise RuntimeError(
                f"解答プログラムが途中で終了した "
                f"(returncode={returncode})"
            )

        self.transcript.append(("Solution", line))

        return line

    def finish(self):
        """
        正解判定後、解答プログラムが正常終了するか確認。
        """

        if self.proc.stdin and not self.proc.stdin.closed:
            self.proc.stdin.close()

        try:
            self.proc.wait(timeout=TIMEOUT_SECOND)
        except subprocess.TimeoutExpired:
            raise TimeoutError(
                "正解を通知した後もプログラムが終了しなかった"
            )

        if self.proc.returncode != 0:
            raise RuntimeError(
                f"解答プログラムが異常終了した "
                f"(returncode={self.proc.returncode})"
            )

    def stop(self):
        if self.proc.poll() is None:
            self.proc.kill()
            self.proc.wait()

    def print_transcript(self):
        print("===== transcript =====")

        for side, text in self.transcript:
            print(f"{side:8}: {text}")

    def print_stderr(self):
        if self.stderr_lines:
            print("===== stderr =====")
            print("".join(self.stderr_lines), end="")


sol_command = prepare(SOL)

for t in range(TEST_COUNT):
    case = generate()

    io = InteractiveProcess(sol_command)

    try:
        ok, reason = judge(io, case)

        if not ok:
            print("WA")
            print("===== hidden case =====")
            print(repr(case))
            print("===== reason =====")
            print(reason)

            io.print_transcript()
            io.print_stderr()

            with open("failed.txt", "w") as f:
                f.write(repr(case))

            io.stop()
            break

        io.finish()

    except TimeoutError as e:
        print("TLE!")
        print("===== hidden case =====")
        print(repr(case))
        print("===== reason =====")
        print(e)

        io.print_transcript()
        io.print_stderr()

        with open("failed.txt", "w") as f:
            f.write(repr(case))

        io.stop()
        break

    except RuntimeError as e:
        print("RE / Protocol Error!")
        print("===== hidden case =====")
        print(repr(case))
        print("===== reason =====")
        print(e)

        io.print_transcript()
        io.print_stderr()

        with open("failed.txt", "w") as f:
            f.write(repr(case))

        io.stop()
        break

    except Exception as e:
        print("Judge Error!")
        print("===== hidden case =====")
        print(repr(case))
        print("===== error =====")
        print(repr(e))

        io.print_transcript()
        io.print_stderr()

        io.stop()
        break

    finally:
        io.stop()

else:
    print("All tests passed!")

・等差数列の和
def rangeSUM(l, r, c):
    return (l+r)*c//2

half = pow(2, -1, MOD)
def rangeSUM(l, r, c):
    return (l+r)%MOD*c%MOD*half%MOD

・等差数列MODカウント
def rangeModCount(l, r, c, m, k = 0):
    if l == r:
        return c if l%m == k else 0
    if c == 1: return -1

    if l > r: l, r = r, l
    if (r-l)%(c-1) != 0: return -1

    d = (r-l)//(c-1)

    GCD = gcd(m, d)
    if l%GCD != k%GCD: return 0
    ng = (k-l)//GCD
    mg = m//GCD
    dg = d//GCD
    f = inverse(ng, dg, mg)
    if c <= f:
        return 0
    else:
        return (c-f-1)//mg+1

・重心分解
size = [-1]*N
maxidx = [-1]*N

@bootstrap
def dfs(n, pre):
    history.append(n)
    cnt = 1
    MAX = -(10**18)
    for i, (v, c) in enumerate(G[n]):
        if v != pre and not used[v]:
            c = yield dfs(v, n)
            cnt += c
            if MAX < c:
                MAX = c
                maxidx[n] = i
    size[n] = cnt
    yield size[n]

@bootstrap
def dfs2(n, L):
    if size[G[n][maxidx[n]][0]] > L//2:
        yield (yield dfs2(G[n][maxidx[n]][0], L))
    yield n

parent = [-1]*N
used = [False]*N
que = deque()
que.append((0, -1))
while que:
    n, p = que.popleft()
    history = []
    dfs(n, -1)
    center = dfs2(n, len(history))
    while history:
        h = history.pop()
        size[h] = -1
        maxidx[h] = -1
    used[center] = True
    parent[center] = p
    for v, _ in G[center]:
        if not used[v]:
            que.append((v, center))

・ダブリング
class Doubling:
    def __init__(self, nex, max_k=10**18):
        self.N = len(nex)
        self.LOG = max(1, max_k.bit_length())
        self.dp = [[-1]*self.N for _ in range(self.LOG)]
        self.dp[0] = nex[:]
        for i in range(1, self.LOG):
            for j in range(self.N):
                self.dp[i][j] = self.dp[i-1][self.dp[i-1][j]]

    def jump(self, n, k):
        for i in range(self.LOG):
            if 1<<i & k:
                n = self.dp[i][n]
        return n

・LIS
def LIS_length(A, strict=True):
    dp = []
    bisect = bisect_left if strict else bisect_right

    for a in A:
        idx = bisect(dp, a)
        if idx == len(dp):
            dp.append(a)
        else:
            dp[idx] = a

    return len(dp)

def LIS(A, strict=True):
    N = len(A)
    dp = []
    idx = []
    pre = [-1]*N

    bisect = bisect_left if strict else bisect_right

    for i, a in enumerate(A):
        j = bisect(dp, a)
        if j == len(dp):
            dp.append(a)
            idx.append(i)
        else:
            dp[j] = a
            idx[j] = i
        if j:
            pre[i] = idx[j-1]

    ans = []
    if idx:
        now = idx[-1]
        while now != -1:
            ans.append(now)
            now = pre[now]

    return ans[::-1]

・トポロジカルソート
def TopologicalSort(G):
    N = len(G)
    cnt = [0]*N
    for n in range(N):
        for v in G[n]:
            cnt[v] += 1
    que = deque()
    for n in range(N):
        if cnt[n] == 0:
            que.append(n)
    ans = []
    while que:
        n = que.popleft()
        ans.append(n)
        for v in G[n]:
            cnt[v] -= 1
            if cnt[v] == 0:
                que.append(v)
    return ans if len(ans) == N else None

・トポロジカルソート（辞書順最小）
def TopologicalSortSmall(G):
    N = len(G)
    cnt = [0]*N
    for n in range(N):
        for v in G[n]:
            cnt[v] += 1
    que = []
    for n in range(N):
        if cnt[n] == 0:
            heappush(que, n)
    ans = []
    while que:
        n = heappop(que)
        ans.append(n)
        for v in G[n]:
            cnt[v] -= 1
            if cnt[v] == 0:
                heappush(que, v)
    return ans if len(ans) == N else None

・転倒数（順列）
# Pは0～N-1の順列
def InversionNumber(P):
    N = len(P)
    B = BIT([0]*N)
    ans = 0
    for p in P:
        if p+1 < N:
            ans += B.query(p+1, N)
        B.add(p, 1)
    return ans

・転倒数
def InversionNumber(A):
    D = compress(A)
    L = len(D)
    B = BIT([0]*L)
    ans = 0
    for a in A:
        idx = D[a]
        if idx+1 < L:
            ans += B.query(idx+1, L)
        B.add(idx, 1)
    return ans

・オイラーツアー（部分木）
class EulerTour:
    def __init__(self, G, root=0):
        self.G = G
        self.N = len(self.G)
        self.IN = [-1]*self.N
        self.OUT = [-1]*self.N
        self.REV = [-1]*self.N
        self.dfs(root, -1, 0)

    @bootstrap
    def dfs(self, n, pre, time):
        self.IN[n] = time
        self.REV[time] = n
        for v in self.G[n]:
            if v == pre:
                continue
            time = yield self.dfs(v, n, time+1)
        self.OUT[n] = time
        yield time

    def index(self, n):
        return self.IN[n]

    def interval(self, n):
        return (self.IN[n], self.OUT[n])

    def index_rev(self, n):
        return self.REV[n]

・オイラーツアー（パス（辺））
class EulerTour:
    def __init__(self, G, root=0):
        self.G = G
        self.N = len(self.G)
        self.IN = [-1]*(self.N-1)
        self.OUT = [-1]*(self.N-1)
        self.REV = [-1]*((self.N-1)*2)
        self.dfs(root, -1, 0)

    @bootstrap
    def dfs(self, n, pre, time):
        for v, eidx in self.G[n]:
            if v == pre:
                continue
            self.IN[eidx] = time
            self.REV[time] = eidx
            time += 1
            time = yield self.dfs(v, n, time)
            self.OUT[eidx] = time
            self.REV[time] = eidx
            time += 1
        yield time

    def index_in(self, n):
        return self.IN[n]

    def index_out(self, n):
        return self.OUT[n]

    def interval(self, n):
        return (self.IN[n], self.OUT[n])

    def index_rev(self, n):
        return self.REV[n]

・オイラーツアー（パス（頂点））
class EulerTour:
    def __init__(self, G, root=0):
        self.G = G
        self.N = len(self.G)
        self.IN = [-1]*self.N
        self.OUT = [-1]*self.N
        self.REV = [-1]*(self.N*2)
        self.dfs(root, -1, 0)

    @bootstrap
    def dfs(self, n, pre, time):
        self.IN[n] = time
        self.REV[time] = n
        time += 1
        for v in self.G[n]:
            if v == pre:
                continue
            time = yield self.dfs(v, n, time)
        self.OUT[n] = time
        self.REV[time] = n
        time += 1
        yield time

    def index_in(self, n):
        return self.IN[n]

    def index_out(self, n):
        return self.OUT[n]

    def interval(self, n):
        return (self.IN[n], self.OUT[n])

    def index_rev(self, n):
        return self.REV[n]