# ============================================================
# 競プロライブラリ 使用例集
# ============================================================
# ※ ライブラリ本体を上に貼り付けてから使用する
# ※ 変数名の使い回しは気にしない
# ============================================================


# ============================================================
# 1. 入力
# ============================================================

# 文字列を1個読み込む
s = I()

# 整数を1個読み込む
n = II()

# 空白区切りの文字列
a = IS()

# 空白区切りの整数
a = MI()

# 文字列リスト
a = LS()

# 整数リスト
a = LI()

# 文字列を1文字ずつ取得
a = LC()

# 整数を0-index化
a = MI0()

# 整数リストを0-index化
a = LI0()


# ============================================================
# 2. 階乗・組合せ
# ============================================================

mod = 998244353

# 5! を計算
x = Factorial(5, mod)

# 0! ～ 10! を配列として取得
fact = FactorialList(10, mod)

# nCk を計算
x = CMB(5, 2)

# 最小公倍数
x = LCM(12, 18)


# ============================================================
# 3. 素数
# ============================================================

# 20以下の素数を列挙
primes = eratosthenes(20)

# 12の約数を列挙
divs = divisor(12)

# 60を素因数分解
factors = prime_factorize(60)

# 60を素因数分解して指数も取得
factors = prime_factorize2(60)


# ============================================================
# 4. 幾何
# ============================================================

# 線分 AB と CD が交差するか
a = [0, 0]
b = [4, 4]
c = [0, 4]
d = [4, 0]

print(cross_judge(a, b, c, d))
# True


# ============================================================
# 5. DFS
# ============================================================

# グラフ
graph = [
    [1],
    [2],
    [3],
    []
]

# 0から3までの経路を取得
path = dfs(0, 3, graph)

print(path)
# [0, 1, 2, 3]


# ============================================================
# 6. BFS
# ============================================================

# 重みなしグラフ
graph = [
    [1, 2],
    [0, 3],
    [0, 3],
    [1, 2]
]

# 頂点0から各頂点までの最短距離
dist = bfs(graph, 0)

print(dist)


# ============================================================
# 7. Dijkstra
# ============================================================

# graph[u] = [(行き先, 辺の重み), ...]
graph = [
    [(1, 2), (2, 5)],
    [(2, 1)],
    []
]

# 頂点0からの最短距離
dist = dijkstra(graph, 0)

print(dist)
# [0, 2, 3]


# ============================================================
# 8. BIT
# ============================================================

# 要素数5のBITを作成
# ※ このBITは1-indexed
bit = BIT(5)

# i番目にxを加算
bit.add(1, 10)
bit.add(2, 20)
bit.add(3, 30)

# 1～iの和
print(bit.sum(2))
# 30


# ============================================================
# 9. 転倒数
# ============================================================

# 転倒数を計算
a = [3, 1, 2]

ans = InversionNumberByBIT(a)

print(ans)
# 2


# 値が大きい場合はこちら
a = [100, 20, 50]

ans = InversionNumberByBIT2(a)

print(ans)


# ============================================================
# 10. 座標圧縮
# ============================================================

a = [100, 500, 100, 20]

# 値の大小関係を保ったまま整数に圧縮
b = zaatsu(a)

print(b)
# [2, 3, 2, 1]


# ============================================================
# 11. LIS
# ============================================================

a = [3, 1, 2, 5, 4]

# 最長増加部分列の長さ
ans = LIS(a)

print(ans)
# 3


# ============================================================
# 12. 行列積
# ============================================================

a = [
    [1, 2],
    [3, 4]
]

b = [
    [5, 6],
    [7, 8]
]

# 行列積
c = mat_mul(a, b, mod)

print(c)


# ============================================================
# 13. 行列累乗
# ============================================================

a = [
    [1, 1],
    [1, 0]
]

# 行列Aの5乗
b = mat_pow(a, 5, mod)

print(b)


# ============================================================
# 14. UnionFind
# ============================================================

uf = UnionFind(5)

# 0と1を同じ集合にする
uf.union(0, 1)

# 1と2を同じ集合にする
uf.union(1, 2)

# 同じ集合か
print(uf.same(0, 2))
# True

print(uf.same(0, 3))
# False

# 0が属する集合のサイズ
print(uf.size(0))

# 0が属する集合のメンバー
print(uf.members(0))

# 各集合の代表元
print(uf.roots())

# 集合の個数
print(uf.group_count())

# 全集合のメンバー
print(uf.all_group_members())


# ============================================================
# 15. WeightedUnionFind
# ============================================================

uf = WeightedUnionFind(3)

# weight[0] - weight[1] = 3
uf.union(0, 1, 3)

# weight[1] - weight[2] = 5
uf.union(1, 2, 5)

# 0と2が同じ集合か
print(uf.same(0, 2))

# weight[0] - weight[2] を取得
print(uf.diff(0, 2))


# ============================================================
# 16. Kruskal
# ============================================================

# graph[u] = [(v, weight), ...]
graph = [
    [(1, 3), (2, 1)],
    [(0, 3), (2, 2)],
    [(0, 1), (1, 2)]
]

# 最小全域木
weight, edges = kruskal(graph)

print(weight)
print(edges)


# ============================================================
# 17. なもりグラフ / Functional Graph
# ============================================================

# 各頂点から出る辺が1本
to = [1, 2, 0, 4, 3]

# サイクルを抽出
cycles = get_cycles(to)

print(cycles)
# [[0, 1, 2], [3, 4]]


# ============================================================
# 18. FunctionalGraph
# ============================================================

to = [1, 2, 0, 4, 3]

fg = FunctionalGraph(len(to), to)

# 頂点0から1回進んだ先
print(fg.get_next(0, 1))
# 1

# 頂点0から5回進んだ先
print(fg.get_next(0, 5))
# 2


# ============================================================
# 19. 通常のSegment Tree
# ============================================================

a = [1, 2, 3, 4, 5]

# 区間和を管理するSegment Tree
seg = SegTree(
    a,
    lambda x, y: x + y,
    0
)

# [l, r) の区間クエリ
print(seg.query(1, 4))
# 2 + 3 + 4 = 9

# i番目をxに変更
seg.update(2, 100)

# i番目にxを加算
seg.add(2, 10)


# ============================================================
# 20. Lazy Segment Tree : 区間加算
# ============================================================

a = [1, 2, 3, 4, 5]

seg = LazySegTree_RAQ(
    a,
    lambda x, y: max(x, y),
    -10**18
)

# [1, 4) に10を加算
seg.add(1, 4, 10)

# [1, 4) をクエリ
print(seg.query(1, 4))


# ============================================================
# 21. Lazy Segment Tree : 区間代入
# ============================================================

a = [1, 2, 3, 4, 5]

seg = LazySegTree_RUQ(
    a,
    lambda x, y: max(x, y),
    -10**18
)

# [1, 4) をすべて100にする
seg.update(1, 4, 100)

# [1, 4) をクエリ
print(seg.query(1, 4))


# ============================================================
# 22. SortedList
# ============================================================

# 最大値が2^20未満の整数を管理
s = SortedList(20)

# 要素を追加
s.insert(5)
s.insert(2)
s.insert(5)
s.insert(8)

# [2, 5, 5, 8]
print(s.to_list())

# 要素数
print(len(s))

# ソート順でi番目
print(s[1])

# x以上の最初の位置
print(s.bisect_left(5))

# xより大きい最初の位置
print(s.bisect_right(5))

# xを1個削除
s.eject(5)

# xを全部削除
s.remove(5)

# i番目を削除
s.pop(0)

# xより大きい最小値
print(s.min(5))

# xより小さい最大値
print(s.max(5))


# ============================================================
# 23. SortedSet
# ============================================================

# 重複しないソート済み集合
s = SortedSet([5, 2, 8, 2])

print(s)
# [2, 5, 8]

# 要素追加
s.add(10)

# 要素削除
s.discard(5)

# 存在判定
print(8 in s)

# i番目
print(s[0])

# x未満で最大
print(s.lt(5))

# x以下で最大
print(s.le(5))

# xより大きくて最小
print(s.gt(5))

# x以上で最小
print(s.ge(5))

# x未満の要素数
print(s.index(5))

# x以下の要素数
print(s.index_right(5))


# ============================================================
# 24. LCA
# ============================================================

# 木
graph = [
    [1, 2],
    [0, 3, 4],
    [0],
    [1],
    [1]
]

# 根を0としてLCAを前計算
lca = LCAFinder(graph, 0)

# 3と4のLCA
print(lca.lca(3, 4))
# 1


# ============================================================
# 25. FFT / 畳み込み
# ============================================================

fft = FFT(998244353)

a = [1, 2, 3]
b = [4, 5]

# 多項式の積
c = fft.convolution(a, b)

print(c)
# [4, 13, 22, 15]


# ============================================================
# 26. Merge Sort Tree
# ============================================================

a = [3, 1, 4, 2, 5]

# 構築
N0, data = construct(len(a), a)

# [l,r) の中で「値 <= k」の個数
ans = query1(N0, data, 1, 4, 3)

print(ans)

# [l,r) の中で「x <= 値 < y」の個数
ans = query(N0, data, 1, 5, 2, 5)

print(ans)


# ============================================================
# 27. Implicit Treap
# ============================================================

# 「位置」を基準に配列を管理するTreap
tr = ImplicitTreap()

# 位置0に10を挿入
tr.insert(0, 10)

# 位置1に20を挿入
tr.insert(1, 20)

# 位置1に30を挿入
tr.insert(1, 30)

print(tr.to_list())
# [10, 30, 20]

# i番目の値を取得
print(tr.get(1))
# 30

# i番目を削除して値を取得
x = tr.pop(1)

# i番目を削除
tr.erase(1)

# [l,r) を反転
tr.reverse(0, 2)

# [l,r) にxを加算
tr.apply(0, 2, 10)

# [l,r) をすべてxにする
tr.assign(0, 2, 100)

# [l,r) の総和
print(tr.prod(0, 2))

# 要素数
print(tr.size())

# 全要素をリスト化
print(tr.to_list())


# ============================================================
# 28. Treap
# ============================================================

# ソート順を維持するMultiset
tr = Treap([1, 2, 2, 5])

# 値を追加
tr.insert(3)

print(tr.to_list())
# [1, 2, 2, 3, 5]

# x以上の最初の位置
print(tr.bisect_left(2))
# 1

# xより大きい最初の位置
print(tr.bisect_right(2))
# 3

# ソート順でi番目
print(tr.get(2))
# 2

# xを1個削除
tr.erase_one(2)

# x未満の値の総和
print(tr.sum_prefix(5))

# x以下の値の総和
print(tr.sum_prefix_right(5))

# l <= x < r の値の総和
print(tr.prod(2, 5))

# 全要素をリスト化
print(tr.to_list())