【AtCoder】文系大学生が青色になるまで

### 【AtCoder】文系大学生がアルゴリズム・ヒューリスティックで青色になるまで（色変記事）🚶‍♂️🏔
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">ABC265で念願の青色を達成しました🎉<a href="https://twitter.com/hashtag/AtCoder?src=hash&amp;ref_src=twsrc%5Etfw">#AtCoder</a> <a href="https://twitter.com/hashtag/ABC265?src=hash&amp;ref_src=twsrc%5Etfw">#ABC265</a> <a href="https://t.co/5amuhTkgL1">pic.twitter.com/5amuhTkgL1</a></p>&mdash; cozy_sauna (@cozy_sauna) <a href="https://twitter.com/cozy_sauna/status/1561352864874000385?ref_src=twsrc%5Etfw">August 21, 2022</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

# 自己紹介 🥴
- cozy_sauna（サウナが大好きです🧖）
- [Doer（同志社大学プログラミングサークル）](https://doer.vercel.app/)在籍
- **文系学部（国際系）4回生**
- Pythonで参加🐍
- コンテスト初参加・Python学習スタート【2021/1/9 (ARC111)】
- ヒューリスティック青色達成🎉【2022/2/26(AHC008)】
- アルゴリズム青色達成🎉【2022/8/21(ABC265)】
- ICPCアジア地区大会2022参加予定🍨
- [AtCoder【cozy_sauna】](https://atcoder.jp/users/cozy_sauna)

### 競プロを始めるまでは
- プログラミング未経験🧑‍💻
    → Pythonって…ニシキヘビ？🐍🐍
    → JavaScript？なんじゃそりゃ…（語感踏みなら、讃岐うどんだな…)
    → HTML, CSSを少しだけ授業で習った
- 高校数学（数Ⅲまで）は分かる！大学数学（行列など）は全く…🔢

# History 🚶‍♂️
![スクリーンショット 2022-12-09 0.13.44.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1075678/2d5ea763-cca7-8c3c-f6ac-793062411d71.png)
![スクリーンショット 2022-12-09 0.14.10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1075678/1b16f2e3-a775-f048-41f0-056cc3bcabc9.png)

<img width="1000px" alt="スクリーンショット 2022-12-09 0.19.56.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1075678/092513f5-b5c6-b929-bcb2-bad150f2abfa.png">

<img width="1000px" alt="スクリーンショット 2022-12-09 0.20.45.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1075678/4be1e6cf-9169-84b0-2278-d396d6f1fcee.png">

<img width="1000px" alt="スクリーンショット 2022-12-09 3.38.27.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1075678/e7092860-9665-7b77-a8de-6523b6dd50e0.png">

<img width="1000px" alt="スクリーンショット 2022-12-09 3.40.14.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1075678/9228b367-23d6-cf52-c0a6-0c77360a252f.png">


# やったこと🏋️‍♀️
## 基本的には...
■ 習うより慣れろ!問題をガツガツ解くぞ!スタイル⚔️
　　→ [AtCoderProblems](https://kenkoooo.com/atcoder#/table/)を使用しました
　　→ 競プロ本は使用していません（書籍での学習は苦手です...📚）
■ コンテストにはできる限り参加する🖥
　　→ 競プロを始めた日にもARCに参加していました😇
■ 問題を解く→復習→問題を解く…をひたすら繰り返す♻️

## 灰色🐘茶色🐿
■ Pythonの入力受け取りを覚える
　　→【参考記事】https://qiita.com/jamjamjam/items/e066b8c7bc85487c0785
■ 動画で、Pythonの文法を覚える
　　→ 競プロYouTuberのcatupperさんのYouTubeで学習を行いました
　　→ 本当に分かりやすく、始めたての頃は一日中動画を見ていた記憶があります
　　→【参考動画】[catupperさん](https://www.youtube.com/@user-xv5cr2lx3t/videos)
■ 問題を解く⇔復習
　　→問題を解く⇔動画で復習 or 人のコードを見る、これをひたすら繰り返しました

## 緑色🍀
■ 問題を解く中で出会ったアルゴリズムをライブラリ化をしました
■ AtCoderのスニペットを整理しました
　　→ご自由にお使いください 😝

<details><summary>AtCoderスニペット🔥🔥🔥</summary>

```py
from sys import setrecursionlimit, stdin
from collections import defaultdict, deque, Counter
from itertools import permutations, combinations, product
from functools import lru_cache
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop
from copy import copy, deepcopy
from decimal import Decimal
# from pypyjit import set_param
# set_param('max_unroll_recursion=-1')
 
setrecursionlimit(1 << 20)
readline = stdin.readline
INF = 10 ** 18
MOD = 998244353
# MOD = 1000000007
DYDX = [(-1, 0), (1, 0), (0, -1), (0, 1)]
ALP = 26
''' Input '''
def I(): return int(readline())
def ST(): return readline()[:-1]
def LI(): return list(map(int, readline().split()))
def LII(): return list(map(lambda x: int(x) - 1, readline().split()))
def LF(x, func): return [func() for _ in [0] * x]
def SPI(): return map(int, readline().split())
def SPII(): return map(lambda x: int(x) - 1, readline().split())
def FIE(x): return [readline()[:-1] for _ in [0] * x]
 
''' Array '''
def cmin(dp, i, x):
    if x < dp[i]: dp[i] = x
def cmax(dp, i, x):
    if x > dp[i]: dp[i] = x
 
''' Alphabet '''
def id_a(s): return ord(s) - ord('a')
def id_A(s): return ord(s) - ord('A')
def st_a(i): return chr(ord('a') + i)
def st_A(i): return chr(ord('A') + i)
 
''' Other'''
def ranges(*args): return [(i, j) for i in range(args[0]) for j in range(args[-1])]
def nynx(y, x, ly = INF, lx = INF): return [(y + dy, x + dx) for dy, dx in DYDX if 0 <= y + dy < ly and 0 <= x + dx < lx]
def gen(x, *args):
    if len(args) == 1: return [x] * args[0]
    if len(args) == 2: return [[x] * args[1] for _ in [0] * args[0]]
    if len(args) == 3: return [[[x] * args[2] for _ in [0] * args[1]] for _ in [0] * args[0]]
    if len(args) == 4: return [[[[x] * args[3] for _ in [0] * args[2]] for _ in [0] * args[1]] for _ in [0] * args[0]]
 
''' Output '''
def puts(E):
    for e in E: print(e)
def pprint(E): 
    print()
    for e in E: print(e)
def Yes(): print("Yes")
def No(): print("No")
def YES(): print("YES")
def NO(): print("NO")
def yn(x): print("Yes" if x else "No")
def YN(x): print("YES" if x else "NO")
###############################################################################################
print("ここからコードを書き始めます")
```
</details>

## 水色🐳
■ バーチャルコンテストに参加する
　　→ レートが頭打ちになったため、コンテストで難しい問題を解く方針ではなく、簡単な問題を速く解いてレートを上げる方針に変更しました。
　　→ 簡単な問題に慣れるため、可能であれば毎日下記バーチャルコンテストに参加しました。
| コンテスト名| 詳細|
| :---: | :---: | 
|☕あさかつ|毎朝7時半〜8時半に開催されています|
|🌽まよコン|毎日夜9時〜10時40分に開催されています|

（※バーチャルコンテストは[AtCoderProblems](https://kenkoooo.com/atcoder#/table/)から参加することができます）

## 青色🫐
■ 約1年半で青色達成しました🎉 青色を目標にしていたので、とても嬉しいです

# 学習したアルゴリズム一覧
■ アルゴリズムをクリックするとPythonでの実装コードを確認できます↓
| 🐈| 🐈‍⬛| 🐈|
| :---: | :---: | :---: |
|[約数列挙](https://github.com/cozysauna/competitive-programming-python/blob/master/prime/divisors.py)|[素数判定](https://github.com/cozysauna/competitive-programming-python/blob/master/prime/is_prime.py)|[素因数分解](https://github.com/cozysauna/competitive-programming-python/blob/master/prime/prime_factorize.py)|
|[エラトステネスの篩](https://github.com/cozysauna/competitive-programming-python/blob/master/prime/sieve_of_eratosthenes.py)|[オイラーのファイ関数](https://github.com/cozysauna/competitive-programming-python/blob/master/prime/totient.py)|[ベルマンフォード](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/bellman_ford.py)|
|[ワーシャルフロイド](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/warshall_froyd.py)|[ダイクストラ](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/dijkstra.py)|セグメント木|
|遅延セグメント木|[BIT(Binary Indexed Tree)](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/bit.py)|[二次元BIT](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/bit_2d.py)|
|[Dinic](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/dinic.py)|[LCA（最近共通祖先）](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/euler_tour.py)|[長増加部分列](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/lis.py)|
|[関節点・橋](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/lowlink.py)|[最小費用流問題](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/min_cost_flow.py)|[最小全域木](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/prim.py)|
|[全方位木DP](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/rerooting.py)|[強連結成分分解](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/scc.py)|[トポロジカルソート](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/topological_sort.py)|
|[木の直径](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/tree_diameter.py)|[Union-Find](https://github.com/cozysauna/competitive-programming-python/blob/master/graph/union_find.py)|[カタラン数](https://github.com/cozysauna/competitive-programming-python/blob/master/number/catalan_number.py)|
|[座標圧縮](https://github.com/cozysauna/competitive-programming-python/blob/master/number/compress.py)|[中国剰余定理](https://github.com/cozysauna/competitive-programming-python/blob/master/number/crt.py)|[累積和](https://github.com/cozysauna/competitive-programming-python/blob/master/number/cumsum.py)
|[二次元累積和](https://github.com/cozysauna/competitive-programming-python/blob/master/number/cumsum2d.py)|[ダブリング](https://github.com/cozysauna/competitive-programming-python/blob/master/number/doubling.py)|[拡張ユークリッド](https://github.com/cozysauna/competitive-programming-python/blob/master/number/ext_gcd.py)|
|[gcd](https://github.com/cozysauna/competitive-programming-python/blob/master/number/gcd.py)・[lcm](https://github.com/cozysauna/competitive-programming-python/blob/master/number/lcm.py)|逆元（[逆元nCr](https://github.com/cozysauna/competitive-programming-python/blob/master/number/nCr_inverse.py)、[逆元階乗](https://github.com/cozysauna/competitive-programming-python/blob/master/number/inv_number_and_factorial.py)）|[転倒数](https://github.com/cozysauna/competitive-programming-python/blob/master/number/inversion.py)|
|[部分和問題](https://github.com/cozysauna/competitive-programming-python/blob/master/number/partial_sum.py)|[ポップカウント](https://github.com/cozysauna/competitive-programming-python/blob/master/number/pop_cnt.py)|[部分集合](https://github.com/cozysauna/competitive-programming-python/blob/master/number/subset.py)|
|[レーベンシュタイン距離](https://github.com/cozysauna/competitive-programming-python/blob/master/string/levenshtein_distance.py)|[ローリングハッシュ](https://github.com/cozysauna/competitive-programming-python/blob/master/string/rollinghash.py)|[ランレングス圧縮](https://github.com/cozysauna/competitive-programming-python/blob/master/string/run_length_encoding.py)|
|[行列アフィン変換](https://github.com/cozysauna/competitive-programming-python/blob/master/matrix/affine_transformation.py)|[行列フィボナッチ数列](https://github.com/cozysauna/competitive-programming-python/blob/master/matrix/fibonacci.py)|[行列積](https://github.com/cozysauna/competitive-programming-python/blob/master/matrix/mat_mul.py)・[行列累乗](https://github.com/cozysauna/competitive-programming-python/blob/master/matrix/mat_pow.py)|

# vscode ユーザースニペット🆚👩‍💻
■ ユーザスニペットに下記を設定すると、_アルゴリズム名と打つだけで、アルゴリズムコードがでてきます！
■ また_mainと打つとmainのAtCoderのスニペットが登場します。
<details><summary>ユーザースニペット🔥🔥</summary>

```
{
	// main
	"main": {
		"prefix": "_main",
		"body": [
			"from sys import setrecursionlimit, stdin",
			"from collections import defaultdict, deque, Counter",
			"from itertools import permutations, combinations, product",
			"from functools import lru_cache",
			"from bisect import bisect_left, bisect_right",
			"from heapq import heappush, heappop",
			"from copy import copy, deepcopy",
			"from decimal import Decimal",
			"# from pypyjit import set_param", 
			"# set_param('max_unroll_recursion=-1')",
			"",
			"setrecursionlimit(1 << 20)",
			"readline = stdin.readline",
			"INF = 10 ** 18",
			"MOD = 998244353",
			"# MOD = 1000000007",
			"DYDX = [(-1, 0), (1, 0), (0, -1), (0, 1)]",
			"ALP = 26",
			"''' Input '''",
			"def I(): return int(readline())",
			"def ST(): return readline()[:-1]",
			"def LI(): return list(map(int, readline().split()))",
			"def LII(): return list(map(lambda x: int(x) - 1, readline().split()))",
			"def LF(x, func): return [func() for _ in [0] * x]",
			"def SPI(): return map(int, readline().split())",
			"def SPII(): return map(lambda x: int(x) - 1, readline().split())",
			"def FIE(x): return [readline()[:-1] for _ in [0] * x]",

			"''' Array '''",
			"def cmin(dp, i, x):",
			"    if x < dp[i]: dp[i] = x",
			"def cmax(dp, i, x):",
			"    if x > dp[i]: dp[i] = x",
			"",
			"''' Alphabet '''",
			"def id_a(s): return ord(s) - ord('a')",
			"def id_A(s): return ord(s) - ord('A')",
			"def st_a(i): return chr(ord('a') + i)",
			"def st_A(i): return chr(ord('A') + i)",
			"",
			"''' Other'''",
			"def ranges(*args): return [(i, j) for i in range(args[0]) for j in range(args[-1])]",
			"def nynx(y, x, ly = INF, lx = INF): return [(y + dy, x + dx) for dy, dx in DYDX if 0 <= y + dy < ly and 0 <= x + dx < lx]",
			"def gen(x, *args):",
			"    if len(args) == 1: return [x] * args[0]",
			"    if len(args) == 2: return [[x] * args[1] for _ in [0] * args[0]]",
			"    if len(args) == 3: return [[[x] * args[2] for _ in [0] * args[1]] for _ in [0] * args[0]]",
			"    if len(args) == 4: return [[[[x] * args[3] for _ in [0] * args[2]] for _ in [0] * args[1]] for _ in [0] * args[0]]",
			
			"''' Output '''",
			"def puts(E):",
			"    for e in E: print(e)",
			"def pprint(E): ",
			"    print()",
			"    for e in E: print(e)",
			"def Yes(): print(\"Yes\")",
			"def No(): print(\"No\")",
			"def YES(): print(\"YES\")",
			"def NO(): print(\"NO\")",
			"def yn(x): print(\"Yes\" if x else \"No\")",
			"def YN(x): print(\"YES\" if x else \"NO\")",
			"###############################################################################################",
			"",
			""
		],
		"description": "main"
	},

	// geometry
	"line_equation": {
		"prefix": "_line_equation",
		"body": [
			"# Equation which passes through the two points (x1, y1), (x2, y2)",
			"# (a, b, c) (ax + by + c = 0)",
			"def line_equation(x1, y1, x2, y2): ",
			"    a = y1 - y2 ",
			"    b = x2 - x1 ",
			"    c = y1 * (x1 - x2) - x1 * (y1 - y2)",
			"    return a, b, c ",
			""
		],
		"description": "line_equation"
	},

	"point_line_distance": {
		"prefix": "_point_line_distance",
		"body": [
			"# distance of ax + by + c = 0 and (x, y)",
			"def point_line_distance(a, b, c, x, y):",
			"    return abs(a * x + b * y + c) / (a ** 2 + b ** 2) ** .5",
			""
		],
		"description": "point_line_distance"
	},

	"rot": {
		"prefix": "_rot",
		"body": [
			"def rot(A): return [*map(list, zip(*A[::-1]))]",
			""
		],
		"description": "rot"
	},

	"rot_degree": {
		"prefix": "_rot_degree",
		"body": [
			"from math import pi, sin, cos",
			"",
			"def rot_degree(x, y, d):",
			"    rad = d * pi / 180",
			"    _x = x * cos(rad) - y * sin(rad)",
			"    _y = y * cos(rad) + x * sin(rad)",
			"    return (_x, _y)",
			""
		],
		"description": "rot_degree"
	},

	"rot_radian": {
		"prefix": "_rot_radian",
		"body": [
			"from math import sin, cos",
			"",
			"def rot_radian(x, y, rad):",
			"    _x = x * cos(rad) - y * sin(rad)",
			"    _y = y * cos(rad) + x * sin(rad)",
			"    return (_x, _y)",
			""
		],
		"description": "rot_radian"
	},

	"three_point_circle": {
		"prefix": "_three_point_circle",
		"body": [
			"# (center_x, center_y), radius",
			"def three_point_circle(x1, y1, x2, y2, x3, y3):",
			"    i = 2 * (x1 - x2)",
			"    j = 2 * (y1 - y2)",
			"    k = 2 * (x1 - x3)",
			"    l = 2 * (y1 - y3)",
			"    m = x1 ** 2 - x2 ** 2 + y1 ** 2 - y2 ** 2",
			"    n = x1 ** 2 - x3 ** 2 + y1 ** 2 - y3 ** 2",
			"    deno = k * j - i * l ",
			"    if deno == 0: return (None, None), None",
			"    y = (m * k - n * i) / deno",
			"    x = (n * j - m * l) / deno",
			"    r = (x1 - x) ** 2 + (y1 - y) ** 2",
			"    return (x, y), r ** .5",
			""
		],
		"description": "three_point_circle"
	},

	"triangle_area": {
		"prefix": "_triangle_area",
		"body": [
			"def triangle_area(ax, ay, bx, by, cx, cy): return abs((ax - cx) * (by - cy) - (bx - cx)* (ay - cy)) / 2 ",
			""
		],
		"description": "triangle_area"
	},

	// graph
	"bellman_ford": {
		"prefix": "_bellman_ford",
		"body": [
			"def bellman_ford(N, node, start = 0):",
			"    dist = [10 ** 18] * N",
			"    dist[start] = 0",
			"    for _ in range(N):",
			"        update = False",
			"        for x, y, c in node:",
			"            if dist[y] > dist[x] + c:",
			"                dist[y] = dist[x] + c",
			"                update = True",
			"        if not update: break",
			"        ",
			"    # find negative cycle",
			"    negative_flag = [0] * N",
			"    for _ in range(N):",
			"        for x, y, c in node:",
			"            if dist[x] == 10 ** 18: continue",
			"            if dist[y] > dist[x] + c:",
			"                dist[y] = dist[x] + c",
			"                negative_flag[y] = 1",
			"            if negative_flag[x]: ",
			"                negative_flag[y] = 1",
			"",
			"    return dist, negative_flag",
			""
		],
		"description": "bellman_ford"
	},

	"bit": {
		"prefix": "_bit",
		"body": [
			"class BIT(): # 1-indexed",
			"    def __init__(self, N):",
			"        self.size = N",
			"        self.tree = [0] * (N + 1)",
			"        self.arr = [0] * (N + 1)",
			" ",
			"    # A[i] += x",
			"    def add(self, i, x):",
			"        self.arr[i] += x",
			"        while i <= self.size:",
			"            self.tree[i] += x",
			"            i += i & -i",
			"",
			"    # A[i] = x ",
			"    def update(self, i, x):self.add(i, x - self.arr[i])",
			"",
			"    # A[1] + A[2] + ... + A[i]",
			"    def sum(self, i):",
			"        ret = 0",
			"        while i > 0:",
			"            ret += self.tree[i]",
			"            i -= i & -i",
			"        return ret",
			"",
			"    # A[i]",
			"    def get(self, i): return self.arr[i]",
			"",
			"    # max_i (i <= x and A[i] > 0)",
			"    def less_than_x(self, x):",
			"        base = self.sum(x)",
			"        if base == 0: return None ",
			"        ng, ok = 0, x",
			"        while ok - ng > 1:",
			"            mid = ok + ng >> 1",
			"            if self.sum(mid) == base: ok = mid ",
			"            else: ng = mid ",
			"        return ok ",
			"",
			"    # min_i (i >= x and A[i] > 0)",
			"    def more_than_x(self, x):",
			"        base = self.sum(x - 1)",
			"        if self.get_all_sum() - base == 0: return None ",
			"        ng, ok = x - 1, self.size",
			"        while ok - ng > 1:",
			"            mid = ng + ok >> 1",
			"            if self.sum(mid) - base == 0: ng = mid ",
			"            else: ok = mid ",
			"        return ok",
			"",
			"    def get_all_sum(self): return self.sum(self.size)",
			"",
			"    def display_all(self): print(*self.arr[1:])",
			""
		],
		"description": "bit"
	},

	"bit_2d": {
		"prefix": "_bit_2d",
		"body": [
			"class BIT_2d:",
			"    # 0-indexed",
			"    def __init__(self, H, W):",
			"        self.H = H + 1",
			"        self.W = W + 1",
			"        self.arr = [0] * self.W * self.H",
			"        ",
			"    def add(self, i, j, x):",
			"        i += 1",
			"        j += 1",
			"        _j = j",
			"        arr = self.arr",
			"        H = self.H",
			"        W = self.W",
			"        while i < H:",
			"            j = _j",
			"            while j < W:",
			"                arr[i * W + j] += x",
			"                j += j & - j",
			"            i += i & -i",
			"",
			"    def sum(self, i, j):",
			"        arr = self.arr",
			"        ret = 0",
			"        _j = j",
			"        W = self.W",
			"        while i:",
			"            j = _j",
			"            while j:",
			"                ret += arr[i * W + j]",
			"                j -= j & -j",
			"            i -= i & - i",
			"        return ret",
			"",
			"    # x0 <= x < x1 and y0 <= y < y1",
			"    def range_sum(self, x0, x1, y0, y1):",
			"        return self.sum(x1, y1) - self.sum(x1, y0) - self.sum(x0, y1) + self.sum(x0, y0)",
			""
		],
		"description": "bit_2d"
	},

	"dijksta": {
		"prefix": "_dijkstra",
		"body": [
			"class Dikstra:",
			"    def __init__(self, N, node):",
			"        self.node = node ",
			"        self.N = N ",
			"        self.start_node = None",
			"        self.prev = [None] * N ",
			"",
			"    def get(self, start):",
			"        self.start_node = start",
			"        dist, done = [10 ** 18] * self.N, [0] * self.N",
			"        hq = [(0, start)] # (cost, node)",
			"        dist[start] = 0",
			"        while hq:",
			"            c, v = heappop(hq)",
			"            if done[v]: continue",
			"            done[v] = 1",
			"            for to, cost in self.node[v]: ",
			"                new_cost = dist[v] + cost",
			"                if not done[to] and new_cost < dist[to]:",
			"                    dist[to] = new_cost",
			"                    self.prev[to] = v",
			"                    heappush(hq, (dist[to], to))",
			"        return dist",
			"",
			"    def init_prev(self): self.prev = [None] * self.N",
			"",
			"    def get_path(self, start, to):",
			"        if self.start_node != start:",
			"            self.init_prev()",
			"            self.get(start)",
			"        ",
			"        path = []",
			"        while to != None:",
			"            path.append(to)",
			"            to = self.prev[to]",
			"",
			"        return path[::-1]",
			""
			],
			"description": "dijksta"
	},

	"dinic": {
		"prefix": "_dinic",
		"body": [
			"class Dinic:",
			"    def __init__(self, N):",
			"        self.N = N",
			"        self.node = [[] for _ in range(N)]",
			"",
			"    def add_edge(self, x, y, capacity): # x -> y",
			"        self.node[x].append([y, capacity, len(self.node[y])]) # to, capacity, rev",
			"        self.node[y].append([x, 0, len(self.node[x]) - 1])",
			"",
			"    def bfs(self, start):",
			"        self.level = [-1] * self.N ",
			"        self.level[start] = 0",
			"        que = deque([start])",
			"        while que:",
			"            v = que.popleft()",
			"            for to, capacity, _ in self.node[v]:",
			"                if capacity > 0 and self.level[to] < 0:",
			"                    self.level[to] = self.level[v] + 1",
			"                    que.append(to)",
			"",
			"    def dfs(self, s, t, flow):",
			"        if s == t: return flow ",
			"        for i in range(self.iter[s], len(self.node[s])):",
			"            self.iter[s] = i ",
			"            to, capacity, rev = self.node[s][i]",
			"            if capacity > 0 and self.level[s] < self.level[to]:",
			"                pre_flow = self.dfs(to, t, min(flow, capacity))",
			"                if pre_flow > 0:",
			"                    self.node[s][i][1] -= pre_flow",
			"                    self.node[to][rev][1] += pre_flow",
			"                    return pre_flow",
			"        return 0",
			"",
			"    def flow(self, s, t):",
			"        mx_flow = 0",
			"        while True:",
			"            self.bfs(s)",
			"            if self.level[t] < 0: break",
			"            self.iter = [0] * self.N ",
			"            while True:",
			"                f = self.dfs(s, t, 10 ** 18)",
			"                if f == 0: break ",
			"                mx_flow += f",
			"    ",
			"        return mx_flow",
			""
		],
		"description": "dinic"
	},

	"euler_tour": {
		"prefix": "_euler_tour",
		"body": [
			"class RMQ:",
			"    def __init__(self, array):",
			"        N = len(array)",
			"        self.e = 10 ** 18",
			"        self.num = 1 << (N - 1).bit_length()",
			"        self.tree = [self.e] * 2 * self.num",
			"        self.index = [None] * 2 * self.num ",
			"        for i in range(N):",
			"            self.tree[self.num + i] = array[i]",
			"            self.index[self.num + i] = i ",
			"",
			"        for i in range(self.num - 1, 0, -1):",
			"            if self.tree[2 * i] <= self.tree[2 * i + 1]:",
			"                self.tree[i] = self.tree[2 * i]",
			"                self.index[i] = self.index[2 * i]",
			"            else:",
			"                self.tree[i] = self.tree[2 * i + 1]",
			"                self.index[i] = self.index[2 * i + 1]",
			"",
			"    def query(self, l, r): #(mn, idx)",
			"        l += self.num",
			"        r += self.num",
			"        mn, idx = self.e, None",
			"",
			"        while l < r:",
			"            if l & 1:",
			"                if mn >= self.tree[l]:",
			"                    mn = self.tree[l]",
			"                    idx = self.index[l]",
			"                l += 1",
			"            if r & 1:",
			"                if mn >= self.tree[r - 1]:",
			"                    mn = self.tree[r - 1]",
			"                    idx = self.index[r - 1]",
			"",
			"            l >>= 1",
			"            r >>= 1",
			"        return mn, idx ",
			"",
			"class RSQ:",
			"    def __init__(self, array):",
			"        N = len(array)",
			"        self.e = 0",
			"        self.num = 1 << (N - 1).bit_length()",
			"        self.tree = [self.e] * 2 * self.num",
			"        for i in range(N): self.tree[self.num + i] = array[i]",
			"        for i in range(self.num - 1, 0, -1): self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]",
			"",
			"    def query(self, l, r): # [l, r)",
			"        ret = self.e",
			"        l += self.num",
			"        r += self.num",
			"        while l < r:",
			"            if l & 1: ret += self.tree[l]; l += 1",
			"            if r & 1: ret += self.tree[r - 1]",
			"            l >>= 1",
			"            r >>= 1",
			"        return ret",
			"",
			"class EulerTour:",
			"    def __init__(self, N, node, start = 0):",
			"        self.N = N ",
			"        self.node = node ",
			"        self.info_index = [",
			"            {",
			"                'depth':None, ",
			"                'in': None, ",
			"                'out': None",
			"            } ",
			"            for _ in range(N)",
			"        ]",
			"        self.step = 0",
			"        self._dfs_index(start)",
			"        self.info_step = [",
			"            {",
			"                'now': None, ",
			"                'in_v_cost': None, ",
			"                'in_e_cost': None, ",
			"                'depth': None",
			"            }",
			"            for _ in range(self.step)",
			"        ]",
			"        self._initialize_step()",
			"        self._dfs_step(start)",
			"",
			"        # LCA",
			"        depths = [self.info_step[i]['depth'] for i in range(self.step)]",
			"        self.depth_rmq = RMQ(depths)",
			"",
			"        #subtree_nodes_cost",
			"        nodes = []",
			"        for i in range(self.step):",
			"            _in_v_cost = self.info_step[i]['in_v_cost']",
			"            if _in_v_cost == None: _in_v_cost = 0",
			"            nodes.append(_in_v_cost)",
			"        self.nodes_rsq = RSQ(nodes)",
			"",
			"        #subtree_edges_cost ",
			"        edges = []",
			"        for i in range(self.step):",
			"            _in_e_cost = self.info_step[i]['in_e_cost']",
			"            if _in_e_cost == None: _in_e_cost = 0",
			"            edges.append(_in_e_cost)",
			"        self.edges_rsq = RSQ(edges)",
			"",
			"    def get_lca(self, x, y):",
			"        L = min(self.info_index[x]['in'], self.info_index[y]['in'])",
			"        R = max(self.info_index[x]['out'], self.info_index[y]['out'])",
			"        idx = self.depth_rmq.query(L, R)[1]",
			"        return self.info_step[idx]['now']",
			"",
			"    def get_subtree_nodes_cost(self, x):",
			"        L = self.info_index[x]['in']",
			"        R = self.info_index[x]['out']",
			"        return self.nodes_rsq.query(L, R - 1)",
			"",
			"    def get_subtree_edges_cost(self, x):",
			"        L = self.info_index[x]['in']",
			"        R = self.info_index[x]['out']",
			"        return self.edges_rsq.query(L + 1, R - 1)",
			"",
			"    def _initialize_step(self): self.step = 0",
			"    def _add_step(self): self.step += 1",
			"",
			"    def _dfs_index(self, x, p = -1, depth = 0):",
			"        self.info_index[x]['depth'] = depth",
			"        self.info_index[x]['in'] = self.step",
			"        self._add_step()",
			"        for nx, _ in self.node[x]:",
			"            if nx == p: continue",
			"            self._dfs_index(nx, x, depth + 1)",
			"            self._add_step()",
			"        ",
			"        self.info_index[x]['out'] = self.step",
			"",
			"    def _dfs_step(self, x, p = -1, depth = 0, cost = 0):",
			"        self.info_step[self.step] = {",
			"            'now': x, ",
			"            'in_v_cost': x, ",
			"            'in_e_cost': cost, ",
			"            'depth': depth",
			"        }",
			"        self._add_step()",
			"        for nx, c in self.node[x]:",
			"            if nx == p: continue",
			"            self._dfs_step(nx, x, depth + 1, c)",
			"            self.info_step[self.step] = {",
			"                'now': x, ",
			"                'in_v_cost': None, ",
			"                'in_e_cost': None, ",
			"                'depth': depth",
			"            }",
			"            self._add_step()",
			"",
			"    def verbose(self):",
			"        print('INDEX', *self.info_index, sep = '\\n')",
			"        print('STEP', *self.info_step, sep = '\\n')"
		],
		"description": "euler_tour"
	},

	"lca": {
		"prefix": "_lca",
		"body": [
			"class LCA:",
			"    def __init__(self, node, root = 0):",
			"        self.node = node",
			"        self.root = root",
			"        self.N = len(node)",
			"        self.logn = (self.N - 1).bit_length()",
			"        self.depth = [-1 if i != root else 0 for i in range(self.N)]",
			"        self.parent = [[-1] * self.N for _ in range(self.logn)]",
			"        self.dfs()",
			"        self.doubling()",
			"",
			"    def dfs(self):",
			"        que = [self.root]",
			"        while que:",
			"            u = que.pop()",
			"            for v in self.node[u]:",
			"                if self.depth[v] == -1:",
			"                    self.depth[v] = self.depth[u] + 1",
			"                    self.parent[0][v] = u",
			"                    que.append(v)",
			"",
			"    def doubling(self):",
			"        for i in range(1, self.logn):",
			"            for v in range(self.N):",
			"                if self.parent[i - 1][v] != -1:",
			"                    self.parent[i][v] = self.parent[i - 1][self.parent[i - 1][v]]",
			"",
			"    def get(self, u, v):",
			"        if self.depth[v] < self.depth[u]: u, v = v, u",
			"        du = self.depth[u]",
			"        dv = self.depth[v]",
			"",
			"        for i in range(self.logn):",
			"            if (dv - du) >> i % 2:",
			"                v = self.parent[i][v]",
			"        if u == v: return u",
			"        for i in range(self.logn - 1, -1, -1):",
			"            pu, pv = self.parent[i][u], self.parent[i][v]",
			"            if pu != pv: u, v = pu, pv",
			"",
			"        return self.parent[0][u]",
			""
		],
		"description": "lca"
	},

	"lis": {
		"prefix": "_lis",
		"body": [
			"",
			"def lis(A):",
			"    table = [A[0]]",
			"    for a in A:",
			"        if a > table[-1]: table.append(a)",
			"        else: table[bisect_left(table, a)] = a",
			"    ",
			"    return len(table)",
			""
		],
		"description": "lis"
	},

	"lowlink": {
		"prefix": "_lowlink",
		"body": [
			"class LowLink:",
			"    def __init__(self, N, node, root = 0):",
			"        self.N = N ",
			"        self.node = node ",
			"        self.ord = [None] * N",
			"        self.low = [None] * N",
			"        self.k = 0",
			"        self.root = root ",
			"        self.articulation_points = []",
			"        self.bridges = []",
			"        self.dfs(root)",
			"",
			"    def dfs(self, x, p = -1):",
			"        self.ord[x] = self.k",
			"        self.low[x] = self.k",
			"        self.k += 1",
			"        child = 0",
			"        ap_flag = False ",
			"        for nx in self.node[x]:",
			"            if nx == p: continue ",
			"            if self.ord[nx] == None:",
			"                self.dfs(nx, x)",
			"                self.low[x] = min(self.low[x], self.low[nx])",
			"                child += 1",
			"                if self.ord[x] <= self.low[nx]: ap_flag = True",
			"                if self.ord[x] < self.low[nx]: self.bridges.append((x, nx))",
			"            else:",
			"                self.low[x] = min(self.low[x], self.ord[nx])",
			"        ",
			"        if (x == self.root and child > 1) or (x != self.root and ap_flag):",
			"            self.articulation_points.append(x)",
			"",
			"    def get_bridges(self): return self.bridges",
			"    ",
			"    def get_articulation_points(self): return self.articulation_points",
			""
		],
		"description": "lowlink"
	},

	"min_cost_flow": {
		"prefix": "_min_cost_flow",
		"body": [
			"class MinCostFlow:",
			"    def __init__(self, N):",
			"        self.N = N ",
			"        self.node = [[] for _ in [0] * N]",
			"",
			"    def add_edge(self, x, y, capacity, cost): # x -> y",
			"        self.node[x].append([y, capacity, cost, len(self.node[y])])",
			"        self.node[y].append([x, 0, -cost, len(self.node[x]) - 1])",
			"",
			"    def min_cost_flow(self, x, y, flow):",
			"        ret = 0",
			"        H = [0] * self.N",
			"        prev_v = [0] * self.N ",
			"        prev_e = [0] * self.N",
			"        while flow:",
			"            dist = [INF] * self.N ",
			"            dist[x] = 0",
			"            que = [(0, x)]",
			"            while que:",
			"                c, v = heappop(que)",
			"                if dist[v] < c: continue ",
			"                for i, (to, capacity, cost, _) in enumerate(self.node[v]):",
			"                    new_cost = dist[v] + cost + H[v] - H[to]",
			"                    if capacity > 0 and dist[to] > new_cost:",
			"                        dist[to] = new_cost",
			"                        prev_v[to] = v ",
			"                        prev_e[to] = i",
			"                        heappush(que, (new_cost, to))",
			"",
			"            if dist[y] == INF: return None",
			"            for i in range(self.N): H[i] += dist[i]",
			"",
			"            _flow = flow ",
			"            _y = y ",
			"            while _y != x:",
			"                _flow = min(_flow, self.node[prev_v[_y]][prev_e[_y]][1])",
			"                _y = prev_v[_y]",
			"",
			"            flow -= _flow ",
			"            ret += _flow * H[y]",
			"            _y = y ",
			"            while _y != x:",
			"                e = self.node[prev_v[_y]][prev_e[_y]]",
			"                e[1] -= _flow",
			"                self.node[_y][e[3]][1] += _flow ",
			"                _y = prev_v[_y]",
			"        return ret ",
			""
		],
		"description": "min_cost_flow"
	},

	"prim": {
		"prefix": "_prim",
		"body": [
			"",
			"def prim(node, N):",
			"    ans = 0",
			"    cnt = 0",
			"    que = [(0, 0)]",
			"    done = [0] * N",
			"    while que:",
			"        c, v = heappop(que)",
			"        if done[v]: continue",
			"        done[v] = 1",
			"        cnt += 1",
			"        ans += c",
			"        if cnt == N: break",
			"        for nx, cost in node[v]: ",
			"            if done[nx]: continue",
			"            heappush(que, (cost, nx))",
			"",
			"    return ans"
		],
		"description": "prim"
	},

	"removable_heapq": {
		"prefix": "_removable_heapq",
		"body": [
			"class RemovableHeapq:",
			"    def __init__(self):",
			"        self.que = []",
			"        self.cnt = defaultdict(int)",
			"",
			"    def push(self, x):",
			"        heappush(self.que, x)",
			"        self.cnt[x] += 1",
			"",
			"    def pop(self):",
			"        self._clean_que()",
			"        x = heappop(self.que)",
			"        self.cnt[x] -= 1",
			"        return x ",
			"    ",
			"    def remove(self, x): self.cnt[x] = max(0, self.cnt[x] - 1)",
			"",
			"    def remove_all(self, x): self.cnt[x] = 0",
			"",
			"    def min(self):",
			"        self._clean_que()",
			"        return self.que[0]",
			"    ",
			"    def is_empty(self): ",
			"        self._clean_que()",
			"        return len(self.que) == 0",
			"",
			"    def _clean_que(self):",
			"        while self.que and self.cnt[self.que[0]] == 0: ",
			"            heappop(self.que)",
			""
		],
		"description": "removable_heapq"
	},

	"rerooting": {
		"prefix": "_rerooting",
		"body": [
			"class Rerooting:",
			"    def __init__(self, N, node, e):",
			"        self.dp = [None] * N",
			"        self.node = node ",
			"        self.e = e",
			"        self.ans = [0] * N",
			"",
			"    # Abstraction",
			"    def merge(self, a, b): return max(a, b)",
			"    def fin(self, a): return a + 1",
			"    def build(self, start = 0, initial_cost = 0):",
			"        self._dfs1(start)",
			"        self._dfs2(start, initial_cost)",
			"",
			"    def _dfs1(self, v, p = -1):",
			"        self.dp[v] = [self.e]  * len(self.node[v])",
			"        ret = self.e",
			"        for i, nx in enumerate(self.node[v]):",
			"            if nx == p: continue",
			"            self.dp[v][i] = self._dfs1(nx, v)",
			"            ret = self.merge(ret, self.dp[v][i])",
			"        return self.fin(ret)",
			"",
			"    def _dfs2(self, v, cost, p = -1):",
			"        size = len(self.node[v])",
			"",
			"        for i, nx in enumerate(self.node[v]):",
			"            if nx == p: self.dp[v][i] = cost ",
			"",
			"        cumL = [self.e] * (size + 1)",
			"        cumR = [self.e] * (size + 1)",
			"        for i in range(size): ",
			"            cumL[i + 1] = self.merge(cumL[i], self.dp[v][i])",
			"        for i in range(size)[::-1]:",
			"            cumR[i] = self.merge(cumR[i + 1], self.dp[v][i])",
			"            ",
			"        for i, nx in enumerate(self.node[v]):",
			"            if nx == p: continue",
			"            self._dfs2(nx, self.fin(self.merge(cumL[i], cumR[i + 1])), v)",
			""
		],
		"description": "rerooting"
	},

	"scc": {
		"prefix": "_scc",
		"body": [
			"class SCC:",
			"    def __init__(self, N, node):",
			"        self.N = N",
			"        self.node = node",
			"        self.inv_node = [[] for _ in range(self.N)]",
			"        for i in range(N):",
			"            for v in node[i]:",
			"                self.inv_node[v].append(i)",
			"",
			"        self.order = []",
			"        self.done = [0] * N",
			"        for i in range(N):",
			"            if not self.done[i]: ",
			"                self.dfs(i)",
			"",
			"        self.inv_done = [0] * N",
			"        self.group_members = {}",
			"        self.group = [None] * N",
			"        self.g = 0 # group count",
			"        for v in self.order[::-1]:",
			"            if not self.inv_done[v]:  ",
			"                self.group_members[self.g] = []",
			"                self.inv_dfs(v)",
			"                self.g += 1",
			"",
			"    def dfs(self, x):",
			"        self.done[x] = 1",
			"        for nx in self.node[x]:",
			"            if not self.done[nx]: ",
			"                self.dfs(nx)",
			"        self.order.append(x)",
			"",
			"    def inv_dfs(self, x):",
			"        self.inv_done[x] = 1",
			"        self.group_members[self.g].append(x)",
			"        self.group[x] = self.g",
			"        for nx in self.inv_node[x]:",
			"            if not self.inv_done[nx]: ",
			"                self.inv_dfs(nx)",
			"",
			"    def get_group(self, x): return self.group[x]",
			"",
			"    def same(self, x, y): return self.group[x] == self.group[y]",
			""
		],
		"description": "scc"
	},

	"topological_sort": {
		"prefix": "_topological_sort",
		"body": [
			"def topological_sort(node, N):",
			"    incnt = [0] * N ",
			"    for nxs in node:",
			"        for nx in nxs:",
			"            incnt[nx] += 1",
			"",
			"    que = deque([i for i in range(N) if not incnt[i]])",
			"    ret = []",
			"    while que:",
			"        v = que.popleft()",
			"        ret.append(v)",
			"        for nx in node[v]:",
			"            incnt[nx] -= 1",
			"            if not incnt[nx]:",
			"                que.append(nx)",
			"",
			"    return ret",
			""
		],
		"description": "topological_sort"
	},

	"tree_diameter": {
		"prefix": "_tree_diameter",
		"body": [
			"class TreeDiameter:",
			"    def __init__(self, N, node):",
			"        self.node = node ",
			"        self.N = N",
			"",
			"    def get(self):",
			"        _, mx_idx = self.bfs()",
			"        mx_d, _ = self.bfs(mx_idx)",
			"        return mx_d",
			"",
			"    def bfs(self, start = 0):",
			"        dist = [10 ** 18] * self.N",
			"        q = deque([start])",
			"        dist[start] = 0",
			"        while q:",
			"            v = q.popleft()",
			"            for nx, c in self.node[v]:",
			"                if dist[nx] > dist[v] + c:",
			"                    q.append(nx)",
			"                    dist[nx] = dist[v] + c",
			"        ",
			"        mx_d = max(dist)",
			"        mx_idx = dist.index(mx_d)",
			"        return mx_d, mx_idx",
			""
		],
		"description": "tree_diameter"
	},

	"union_find": {
		"prefix": "_union_find",
		"body": [
			"class UnionFind:",
			"    def __init__(self, n):",
			"        self.n = n",
			"        self.P = [-1] * n # parents",
			"",
			"    def find(self, x):",
			"        if self.P[x] < 0: return x",
			"        self.P[x] = self.find(self.P[x])",
			"        return self.P[x]",
			"",
			"    def union(self, x, y):",
			"        x = self.find(x)",
			"        y = self.find(y)",
			"        if x == y: return",
			"        if self.P[x] > self.P[y]: x, y = y, x",
			"        self.P[x] += self.P[y]",
			"        self.P[y] = x",
			"",
			"    def size(self, x): return -self.P[self.find(x)]",
			"",
			"    def same(self, x, y): return self.find(x) == self.find(y)",
			"",
			"    def members(self, x):",
			"        root = self.find(x)",
			"        return [i for i in range(self.n) if self.find(i) == root]",
			"",
			"    def roots(self): return [i for i, x in enumerate(self.P) if x < 0]",
			"",
			"    def group_count(self): return len(self.roots())",
			"",
			"    def all_group_members(self):",
			"        from collections import defaultdict",
			"        G = defaultdict(list)",
			"        for member in range(self.n): G[self.find(member)].append(member)",
			"        return G",
			"",
			"    def __str__(self): return '\\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())",
			""
		],
		"description": "union_find"
	},

	"warshall_floyd": {
		"prefix": "_warshall_floyd",
		"body": [
			"class WarshallFloyd:",
			"    def __init__(self, N, cost): # (a, b, c) dist[a][b] = c",
			"        self.dist = [[1 << 30] * N for _ in range(N) ]",
			"        for i in range(N): self.dist[i][i] = 0",
			"        for a, b, c in cost:",
			"            self.dist[a][b] = c ",
			"            self.dist[b][a] = c",
			"",
			"        self.prev = [[i] * N for i in range(N)]",
			"        for k in range(N):",
			"            for i in range(N):",
			"                for j in range(N):",
			"                    if self.dist[i][j] > self.dist[i][k] + self.dist[k][j]:",
			"                        self.dist[i][j] = self.dist[i][k] + self.dist[k][j]",
			"                        self.prev[i][j] = self.prev[k][j]",
			"                ",
			"    def get(self, a, b): return self.dist[a][b]",
			"",
			"    def way(self, start, goal):",
			"        cur = goal",
			"        ret = [goal]",
			"        while cur != start:",
			"            cur = self.prev[start][cur]",
			"            ret.append(cur)",
			"        return ret[::-1]",
			""
		],
		"description": "warshall_floyd"
	},

	// matrix
	"affine": {
		"prefix": "_affine",
		"body": [
			"class Affine:",
			"    def __init__(self):",
			"        self.mat = [[1 if i == j else 0 for i in range(3)] for j in range(3)]",
			"",
			"    @staticmethod",
			"    def get(A, x, y):",
			"        M = mat_mul(",
			"            A, ",
			"            [",
			"                [x],",
			"                [y],",
			"                [1]",
			"            ]",
			"        )",
			"",
			"        return (M[0][0], M[1][0])",
			"",
			"    # clock wise",
			"    def rot90(self):",
			"        self.mat = mat_mul(",
			"            [",
			"                [0, 1, 0],",
			"                [-1, 0, 0],",
			"                [0, 0, 1]",
			"            ],",
			"            self.mat",
			"            )",
			"",
			"    # counter clock wise",
			"    def rot90_rev(self):",
			"        self.mat = mat_mul(",
			"            [",
			"                [0, -1, 0],",
			"                [1, 0, 0],",
			"                [0, 0, 1]",
			"            ],",
			"            self.mat",
			"            )",
			"",
			"    # x += t",
			"    def add_x(self, t):",
			"        self.mat = mat_mul(",
			"            [",
			"                [1, 0, t],",
			"                [0, 1, 0],",
			"                [0, 0, 1]",
			"            ],",
			"            self.mat",
			"            )",
			"    ",
			"    # y += t",
			"    def add_y(self, t):",
			"        self.mat = mat_mul(",
			"            [",
			"                [1, 0, 0],",
			"                [0, 1, t],",
			"                [0, 0, 1]",
			"            ],",
			"            self.mat",
			"            )",
			"",
			"    # x -> -x",
			"    def rev_x(self):",
			"        self.mat = mat_mul(",
			"            [",
			"                [-1, 0, 0],",
			"                [0, 1, 0],",
			"                [0, 0, 1]",
			"            ],",
			"            self.mat",
			"            )",
			"",
			"    # y -> -y",
			"    def rev_y(self):",
			"        self.mat = mat_mul(",
			"            [",
			"                [1, 0, 0],",
			"                [0, -1, 0],",
			"                [0, 0, 1]",
			"            ],",
			"            self.mat",
			"        )",
			""
		],
		"description": "affine"
	},

	"fibonacc": {
		"prefix": "_fibonacc",
		"body": [
			"def fibonacci(x):",
			"    return mat_mul(mat_pow([[1, 1], [1, 0]], x), [[1], [0]])[0][0]",
			""
		],
		"description": "fibonacc"
	},
	"mat_mul": {
		"prefix": "_mat_mul",
		"body": [
			"def mat_mul(A, B):",
			"    y, x = len(A), len(A[0])",
			"    yy, xx = len(B), len(B[0])",
			"    if not yy == x: ",
			"        raise Exception('({}, {}) and ({}, {}) cannot be multipled'.format(y, x, yy, xx))",
			"    mat = [[0] * xx for _ in range(y)]",
			"    for i in range(y):",
			"        for j in range(xx):",
			"            mat[i][j] = sum(A[i][k] * B[k][j] for k in range(x))",
			"    return mat ",
			""
		],
		"description": "mat_mul"
	},
	
	"mat_pow": {
		"prefix": "_mat_pow",
		"body": [
			"def mat_pow(A, n):",
			"    if not n: ",
			"        identity_matrix = [[1 if i == j else 0 for i in range(len(A))] for j in range(len(A))]",
			"        return identity_matrix",
			"",
			"    m = mat_pow(A, n//2)",
			"    if n % 2:",
			"        return mat_mul(A, mat_mul(m, m))",
			"    else:",
			"        return mat_mul(m, m)",
			""
		],
		"description": "mat_pow"
	},

	// number
	"subset": {
		"prefix": "_subset",
		"body": [
			"def subset(s):",
			"    t = s ",
			"    while t:",
			"        yield t ",
			"        t = (t - 1) & s ",
			""
		],
		"description": "subset"
	},

	"base_conversion": {
		"prefix": "_base_conversion",
		"body": [
			"# num(x) -> num(y)",
			"def base_conversion(num, x, y):",
			"    k = int(str(num), base = x)",
			"    m = []",
			"    while k:",
			"        d = k % y ",
			"        m.append(d)",
			"        k //= y ",
			"    return ''.join(map(str, m[::-1]))",
			""
		],
		"description": "base_conversion"
	},

	"catalan_number": {
		"prefix": "_catalan_number",
		"body": [
			"def catalan_number(N, MOD):",
			"    F = [1, 1]",
			"    FI = [1, 1]",
			"    INV = [0, 1]",
			"    for i in range(2, 2 * N + 1):",
			"        F.append((F[-1] * i) % MOD)",
			"        INV.append((-INV[MOD % i] * (MOD // i)) % MOD)",
			"        FI.append((FI[-1] * INV[-1]) % MOD)",
			"    return F[2 * N] * FI[N] ** 2 * INV[N + 1] % MOD",
			""
		],
		"description": "catalan_number"
	},

	"compress": {
		"prefix": "_compress",
		"body": [
			"class Compress:",
			"    def __init__(self, A, indexed = 0):",
			"        self.compress = {}",
			"        self.original = {}",
			"        for i, e in enumerate(sorted(set(A))):",
			"            self.compress[e] = i + indexed",
			"            self.original[i + indexed] = e ",
			"",
			"    def get_compress(self, A): ",
			"        if type(A) == list: return [self.compress[e] for e in A]",
			"        if type(A) == int: return self.compress[A]",
			"",
			"    def get_original(self, A): ",
			"        if type(A) == list: return [self.original[e] for e in A]",
			"        if type(A) == int: return self.original[A]",
			""
		],
		"description": "compress"
	},

	"crt": {
		"prefix": "_crt",
		"body": [
			"# x == b1(mod m1) and x == b2(mod m2) 0 <= r < m1 * m2",
			"def crt(b1, m1, b2, m2): ",
			"    d, p, q = ext_gcd(m1, m2)",
			"    if b1 % d != b2 % d: return 0, -1",
			"    m = lcm(m1, m2)",
			"    t = (b2 - b1) // d * p % (m2 // d)",
			"    r = (b1 + m1 * t) % m ",
			"    return r, m ",
			"",
			"def ext_gcd(a, b):",
			"    if a == 0: return (b, 0, 1)",
			"    g, y, x = ext_gcd(b % a, a)",
			"    return g, x - (b // a) * y, y",
			"",
			"def gcd(x, y):",
			"    if x == 0: return y ",
			"    return gcd(y % x, x)",
			"",
			"def lcm(a, b):",
			"    return a // gcd(a,b) * b",
			"",
			""
		],
		"description": "crt"
	},

	"cumsum": {
		"prefix": "_cumsum",
		"body": [
			"class Cumsum:",
			"    def __init__(self, A):",
			"        t, self.cum = 0, [0]",
			"        for a in A: ",
			"            t += a",
			"            self.cum.append(t)",
			"",
			"    #[l, r)",
			"    def get(self, l, r): return self.cum[r] - self.cum[l]",
			""
		],
		"description": "cumsum"
	},

	"cumsum2d": {
		"prefix": "_cumsum2d",
		"body": [
			"class cumsum2d:",
			"    def __init__(self, A):",
			"        H = len(A)",
			"        W = len(A[0])",
			"        self.cum = [[0] * (W + 1) for _ in range(H + 1)] ",
			"",
			"        for i in range(H):",
			"            for j in range(W):",
			"                self.cum[i + 1][j + 1] += self.cum[i + 1][j] + A[i][j]",
			"",
			"        for j in range(W):",
			"            for i in range(H):",
			"                self.cum[i + 1][j + 1] += self.cum[i][j + 1]",
			"",
			"    # i <= y < ii and j <= x < jj",
			"    def get(self, i, ii, j, jj): return self.cum[ii][jj] - self.cum[i][j]",
			""
		],
		"description": "cumsum2d"
	},

	"digital_root": {
		"prefix": "_digital_root",
		"body": [
		  "def digital_root(x):",
		  "    if x == 9: return 9 ",
		  "    return x % 9",
		  ""
		],
		"description": "digital_root"
	},

	"doubling": {
		"prefix": "_doubling",
		"body": [
			"class Doubling:",
			"    def __init__(self, A):",
			"        self.logK = 65",
			"        N = len(A)",
			"        self.db = [[0] * N for _ in range(self.logK)]",
			"        for i in range(N): self.db[0][i] = A[i]",
			"        for k in range(self.logK-1):",
			"            for i in range(N):",
			"                self.db[k+1][i] = self.db[k][self.db[k][i]]",
			" ",
			"    # start -> A[start] -> A[A[start]] ... (loop times)",
			"    def move(self, start, loop):",
			"        now = start",
			"        for k in range(self.logK):",
			"            if loop >> k & 1: now = self.db[k][now]",
			"        return now",
			""
		],
		"description": "doubling"
	},

	"extgcd": {
		"prefix": "_extgcd",
		"body": [
			" # ax + by = d return (x, y, d); d = gcd(a, b)",
			"def extgcd(a, b):",
			"    if not b: return (1, 0, a)",
			"    x, y, d = extgcd(b, a % b)",
			"    return y, x - a // b * y, d",
			""
		],
		"description": "extgcd"
	},

	"factorial": {
		"prefix": "_factorial",
		"body": [
			"def factorial(N, MOD):",
			"    fact = [1]",
			"    for i in range(1, N + 1): fact.append(fact[-1] * i % MOD)",
			"    return fact",
			""
		],
		"description": "factorial"
	},

	"gcd": {
		"prefix": "_gcd",
		"body": [
			"def gcd(x, y):",
			"    while x: x, y = y % x, x ",
			"    return y",
			""
		],
		"description": "gcd"
	},

	"inv_number_and_factorial": {
		"prefix": "_inv_number_and_factorial",
		"body": [
			"def inv_number_and_factorial(N, MOD):",
			"    inv_number = [0, 1]",
			"    inv_fact = [1, 1]",
			"    for i in range(2, N + 1):",
			"        inv_number.append(-inv_number[MOD % i] * (MOD // i) % MOD)",
			"        inv_fact.append((inv_fact[-1] * inv_number[-1]) % MOD)",
			"    return inv_number, inv_fact",
			""
		],
		"description": "inv_number_and_factorial"
	},

	"inv": {
		"prefix": "_inv",
		"body": [
			"class Inv:",
			"    def __init__(self, N, A):",
			"        self.size = N",
			"        self.tree = [0] * (N + 1)",
			"        if 0 in A: ",
			"            for i in range(N): A[i] += 1",
			"        self.A = A",
			"",
			"    def add(self, i, x):",
			"        while i <= self.size:",
			"            self.tree[i] += x",
			"            i += i & -i",
			"",
			"    def sum(self, i):",
			"        ret = 0",
			"        while i > 0:",
			"            ret += self.tree[i]",
			"            i -= i & -i",
			"        return ret",
			"",
			"    def get(self):",
			"        cnt = 0",
			"        for i, a in enumerate(self.A):",
			"            self.add(a, 1)",
			"            cnt += i + 1 - self.sum(a)",
			"        return cnt",
			""
		],
		"description": "inv"
	},

	"lcm": {
		"prefix": "_lcm",
		"body": [
			"def lcm(a, b): return a // gcd(a,b) * b",
			""
		],
		"description": "lcm"
	},

	"mobius": {
		"prefix": "_mobius",
		"body": [
			"def mobius(N):",
			"    is_prime = [1] * (N + 1)",
			"    is_prime[0] = is_prime[1] = 0",
			"    mobius = [0] * (N + 1)",
			"    mobius[1] = 1",
			"    d = [1] * (N + 1)",
			"    for i in range(2, N + 1):",
			"        if d[i] > 1:",
			"            if not i % (d[i] ** 2): mobius[i] = 0",
			"            else: mobius[i] = - mobius[i // d[i]]",
			"        if not is_prime[i]: continue",
			"        mobius[i] = -1",
			"        for j in range(i ** 2, N + 1, i):",
			"            is_prime[j] = 0",
			"            d[j] = i",
			"    return mobius",
			""
		],
		"description": "mobius"
	},

	"nCr": {
		"prefix": "_nCr",
		"body": [
			"from operator import mul",
			"from functools import reduce",
			"",
			"def nCr(n, r):",
			"    r = min(r, n - r)",
			"    numer = reduce(mul, range(n, n - r, -1), 1)",
			"    denom = reduce(mul, range(1, r + 1), 1)",
			"    return numer // denom",
			""
		],
		"description": "nCr"
	},

	"nCr_inverse": {
		"prefix": "_nCr_inverse",
		"body": [
			"class nCrInverse:",
			"    def __init__(self, N, MOD):",
			"        self.N = N ",
			"        self.MOD = MOD ",
			"        self.F = [1, 1]",
			"        self.FI = [1, 1]",
			"        self.INV = [0, 1]",
			"        for i in range(2, self.N + 1):",
			"            self.F.append((self.F[-1] * i) % MOD)",
			"            self.INV.append((-self.INV[MOD % i] * (MOD // i)) % MOD)",
			"            self.FI.append((self.FI[-1] * self.INV[-1]) % MOD)",
			"",
			"    def get(self, n, r):",
			"        if r < 0 or n < r: return 0",
			"        r = min(r, n - r)",
			"        return self.F[n] * self.FI[r] * self.FI[n - r] % self.MOD",
			""
		],
		"description": "nCr_inverse"
	},

	"nPr_inverse": {
		"prefix": "_nPr_inverse",
		"body": [
			"class nPrInverse:",
			"    def __init__(self, N, MOD):",
			"        self.N = N ",
			"        self.MOD = MOD ",
			"        self.F = [1, 1]",
			"        self.FI = [1, 1]",
			"        self.INV = [0, 1]",
			"        for i in range(2, self.N + 1):",
			"            self.F.append((self.F[-1] * i) % MOD)",
			"            self.INV.append((-self.INV[MOD % i] * (MOD // i)) % MOD)",
			"            self.FI.append((self.FI[-1] * self.INV[-1]) % MOD)",
			"",
			"    def get(self, n, r):",
			"        if r < 0 or n < r: return 0",
			"        return self.F[n] * self.FI[n-r] % self.MOD",
			""
		],
		"description": "nPr_inverse"
	},

	"partial_sum": {
		"prefix": "_partial_sum",
		"body": [
			"def partial_sum_cases(A, K, MOD = 998244353):",
			"    if K < 0: return 0",
			"    dp = [0] * (K + 1)",
			"    dp[0] = 1",
			"    for a in A:",
			"        for j in range(K, -1, -1):",
			"            if j + a <= K:",
			"                dp[j + a] += dp[j]",
			"                dp[j + a] %= MOD",
			"",
			"    return dp[K]",
			"",
			"",
			"def partial_sum_judge(A, K):",
			"    if K < 0: return 0",
			"    dp = [False] * (K + 1)",
			"    dp[0] = True ",
			"    for a in A:",
			"        for j in range(K, -1, -1):",
			"            if j + a <= K: ",
			"                dp[j + a] |= dp[j]",
			"                ",
			"    return dp[K]",
			""
		],
		"description": "partial_sum"
	},

	"pop_cnt": {
		"prefix": "_pop_cnt",
		"body": [
			"def pop_cnt(x):",
			"    c = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555)",
			"    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)",
			"    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)",
			"    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)",
			"    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)",
			"    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)",
			"    return c",
			""
		],
		"description": "pop_cnt"
	},

	"recurring_decimal": {
		"prefix": "_recurring_decimal",
		"body": [
			"def gcd(x, y):",
			"    while y: x, y = y, x % y ",
			"    return x ",
			"",
			"def is_terminate_decimal(numerator, denominator):",
			"    div = gcd(numerator, denominator)",
			"    denominator //= div ",
			"    while denominator % 2 == 0: denominator //= 2 ",
			"    while denominator % 5 == 0: denominator //= 5 ",
			"    return denominator == 1",
			"",
			"def recurring_decimal(numerator, denominator):",
			"    # not terminate decimal",
			"    assert not is_terminate_decimal(numerator, denominator)",
			"",
			"    integer, numerator = divmod(numerator, denominator)",
			"    decimal = []",
			"    idx = 0",
			"    checked = {}",
			"    quotient, remainder = divmod(numerator * 10, denominator)",
			"    while (quotient, remainder) not in checked:",
			"        checked[(quotient, remainder)] = idx ",
			"        decimal.append(quotient)",
			"        numerator = remainder",
			"        idx += 1",
			"        quotient, remainder = divmod(numerator * 10, denominator)",
			"",
			"    repeat = decimal[checked[(quotient, remainder)]:]",
			"    ans = str(integer) + '.' + ''.join(map(str, decimal))",
			"    print(ans)",
			"    print(f\"Repeat:{repeat}\")"
		],
		"description": "recurring_decimal"
	},

	"to_int": {
		"prefix": "_to_int",
		"body": [
			"def to_int(x, base): # also supports negative base",
			"    if not x: return ''",
			"    r = (x % abs(base) + abs(base)) % abs(base)",
			"    x = (x - r) // base",
			"    return to_int(x, base) + str(r)",
			""
		],
		"description": "to_int"
	},

	// prime
	"coprime_pairs": {
		"prefix": "_coprime_pairs",
		"body": [
			"# gcd(x, y) = 1(l < x, y, <= r)",
			"def coprime_pairs(l, r):",
			"    ret = (r - l) ** 2",
			"    R = r",
			"    while R > 1:",
			"        a, b = l // R, r // R",
			"        L = max(l // (a + 1), r // (b + 1))",
			"        ret += (L - R) * coprime_pairs(a, b)",
			"        R = L",
			"    return ret",
			""
		],
		"description": "coprime_pairs"
	},

	"divs": {
		"prefix": "_divs",
		"body": [
			"def divs(N):",
			"    i, d, dd = 1, [], []",
			"    while i * i < N:",
			"        if N % i == 0:",
			"            d.append(i)",
			"            dd.append(N // i)",
			"        i += 1",
			"    else:",
			"        if i * i == N and N % i == 0: d.append(i)",
			"    return d + dd[::-1]",
			""
		],
		"description": "divs"
	},

	"is_prime": {
		"prefix": "_is_prime",
		"body": [
			"def is_prime(x):",
			"    if x == 1 or x % 2 == 0: return x == 2",
			"    f = 3",
			"    while f * f <= x:",
			"        if x % f == 0: return False ",
			"        f += 2",
			"    return True ",
			""
		],
		"description": "is_prime"
	},

	"prime_factorize": {
		"prefix": "_prime_factorize",
		"body": [
			"def prime_factorize(N):",
			"    p = defaultdict(int)",
			"    while N % 2 == 0:",
			"        p[2] += 1",
			"        N //= 2",
			"    f = 3",
			"    while f * f <= N:",
			"        if N % f == 0:",
			"            p[f] += 1",
			"            N //= f",
			"        else: f += 2",
			"    if N != 1: p[N] += 1",
			"    return p",
			""
		],
		"description": "prime_factorize"
	},

	"prime_factors": {
		"prefix": "_prime_factors",
		"body": [
			"# 60 = 2 * 2 * 3 * 5 ",
			"# number of prime factors: K[60] = 3",
			"# kinds of prime factors: P[60] = 2, 3, 5  ",
			"",
			"def prime_factors(N):",
			"    K = [0] * (N + 1)",
			"    P = [[] for _ in range(N + 1)]",
			"    for i in range(2, N + 1):",
			"        if K[i]: continue",
			"        for j in range(i, N + 1, i): ",
			"            P[j].append(i)",
			"            K[j] += 1",
			"",
			"    return K[N] ",
			""
		],
		"description": "prime_factors"
	},

	"sieve": {
		"prefix": "_sieve",
		"body": [
			"def sieve(N): ",
			"    P = []",
			"    check = [1] * (N + 1)",
			"    check[1] = 0",
			"    for p in range(2, N + 1):",
			"        if not check[p]: continue",
			"        P.append(p)",
			"        for i in range(p * p, N + 1, p): check[i] = 0",
			"    ",
			"    return P ",
			""
		],
		"description": "sieve"
	},

	"totient": {
		"prefix": "_totient",
		"body": [
			"def totient(n):",
			"    p = defaultdict(int)",
			"    while n % 2 == 0:",
			"        p[2] += 1",
			"        n //= 2",
			"    f = 3",
			"    while f * f <= n:",
			"        if n % f == 0:",
			"            p[f] += 1",
			"            n //= f",
			"        else: f += 2",
			"    if n != 1: p[n] += 1",
			"    ans = 1",
			"    for k, v in p.items():",
			"        ans *= k - 1",
			"        ans *= k ** (v - 1)",
			"",
			"    return ans",
			"",
			"def totient_sieve(N): ",
			"    K = [0] * (N + 1)",
			"    P = [[] for _ in range(N + 1)]",
			"    for i in range(2, N + 1):",
			"        if K[i]: continue",
			"        for j in range(i, N + 1, i): ",
			"            P[j].append(i)",
			"            K[j] = 1",
			"",
			"    sieve = []",
			"    for i, E in enumerate(P):",
			"        ans = i",
			"        for p in E:",
			"            ans //= p",
			"            ans *= p - 1",
			"        sieve.append(ans)",
			"    return sieve",
			""
		],
		"description": "totient"
	},

	// string
	"levenshtein_distance": {
		"prefix": "_levenshtein_distance.py",
		"body": [
			"def levenshtein_distance(A, B): #Edit Distance",
			"    AL = len(A)",
			"    BL = len(B)",
			"    dp = [[10 ** 18] * (BL + 1) for _ in range(AL + 1)]",
			"    dp[0][0] = 0",
			"    for i in range(AL + 1):",
			"        for j in range(BL + 1):",
			"            if i > 0 and j > 0:",
			"                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (A[i - 1] != B[j - 1]))",
			"            if i > 0:",
			"                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)",
			"            if j > 0:",
			"                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)",
			"",
			"    return dp[AL][BL]",
			""
		],
		"description": "levenshtein_distance"
	},

	"rolling_hash": {
		"prefix": "_rolling_hash",
		"body": [
			"class RollingHash:",
			"    def __init__(self, string, base = 1237, mod = (1 << 61) - 1):",
			"        N = len(string)",
			"        self.base = base",
			"        self.mod = mod ",
			"        self.hash = [0] * (N + 1)",
			"        self.p = [1] * (N + 1)",
			"        for i, c in enumerate(string):",
			"            num = ord(c) - ord('a') + 1 ",
			"            self.hash[i + 1] = (self.hash[i] * self.base + num) % self.mod ",
			"            self.p[i + 1] = self.p[i] * base % self.mod",
			"",
			"        ",
			"    def get_hash(self, l, r): #[l, r)",
			"        return (self.hash[r] - self.hash[l] * self.p[r - l]) % self.mod",
			""
		],
		"description": "rolling_hash"
	},

	"run_length_encoding": {
		"prefix": "_run_length_encoding",
		"body": [
			"def rle(S):",
			"    ret = []",
			"    cnt = 1",
			"    pre = S[0]",
			"    for e in S[1:]:",
			"        if e != pre:",
			"            ret.append([pre, cnt])",
			"            cnt = 0",
			"        cnt += 1",
			"        pre = e ",
			"    else:",
			"        ret.append([pre, cnt])",
			"    return ret",
			""
		],
		"description": "run_length_encoding"
	},
}
```
</details>
■ またvscodeにvimプラグインを導入しています🔐 → 実装時間が短くなりました🎉

# 競プロをやっていて良かったこと😆
#### 😊 楽しい 
　　→ 頭を使える良い趣味の一つとなりました
#### 📚 プログラミングを学習するきっかけになった 
　　→ 競プロからWeb開発や機械学習にも興味を持つことができました
#### 🗡 就職活動で武器となった
　　→ 特にコーディングテストで苦戦することはありませんでした
　　→ 面接でのネタ（強み）になりました
　　→ 結果、憧れ企業のエンジニア内定をいただくことができました

#### 🙆‍♂️ 友達が増えた 
　　→ 同じ趣味を持つ友達と話す時間はとても楽しいです
　　→ **Do'erの皆に感謝** 🎉

## 参考記事・動画一覧
・[初心者向けAtcoder標準入力セット(Python)](https://qiita.com/jamjamjam/items/e066b8c7bc85487c0785)
・[かつっぱ競プロ](https://www.youtube.com/@user-xv5cr2lx3t)