cpp.code-snippets

{
	"Multi test": {
		"scope": "cpp",
		"prefix": "multi_test",
		"body": [
			"#include <bits/stdc++.h>",
			"using namespace std;",
			"using ll = long long;",
			"using ii = pair<int, int>;",
			"using llp = pair<ll, ll>;",
			"using vi = vector<int>;",
			"using vii = vector<ii>;",
			"using vvi = vector<vi>;",
			"using vll = vector<ll>;",
			"using vvll = vector<vll>;",
			"template<typename T>",
			"using min_heap = priority_queue<T, vector<T>, greater<T>>;",
			"#define pb push_back",
			"#define fi first",
			"#define se second",
            "#define sz(x)(int)(x).size()",
            "#define rep(i, a, b) for (int i = a; i < (b); ++i)",
            "#define all(x) begin(x), end(x)",
			"#define _ <<\" \"<<",
            "",
            "//#ifndef ONLINE_JUDGE",
            "//   #include \"debug/debug.cpp\"",
            "//#else",
            "//   #define debug(...)",
            "//   #define debugArr(...)",
            "//#endif",
			"",
			"void solve() {",
			"    ",
			"}",
			"",
			"signed main() {",
			"    ios::sync_with_stdio(0);",
			"    cin.tie(0);",
			"    int TC;",
			"    cin >> TC;",
			"    while (TC--) solve();",
			"    return 0;",
			"}"
		],
		"description": "C++ Template with common includes and macros"
	},
	"Single test": {
		"scope": "cpp",
		"prefix": "single_test",
		"body": [
			"#include <bits/stdc++.h>",
			"using namespace std;",
			"using ll = long long;",
			"using ii = pair<int, int>;",
			"using llp = pair<ll, ll>;",
			"using vi = vector<int>;",
			"using vii = vector<ii>;",
			"using vvi = vector<vi>;",
			"using vll = vector<ll>;",
			"using vvll = vector<vll>;",
			"template<typename T>",
			"using min_heap = priority_queue<T, vector<T>, greater<T>>;",
			"#define pb push_back",
			"#define fi first",
			"#define se second",
            "#define sz(x)(int)(x).size()",
            "#define rep(i, a, b) for (int i = a; i < (b); ++i)",
            "#define all(x) begin(x), end(x)",
			"#define _ <<\" \"<<",
            "",
            "//#ifndef ONLINE_JUDGE",
            "//   #include \"debug/debug.cpp\"",
            "//#else",
            "//   #define debug(...)",
            "//   #define debugArr(...)",
            "//#endif",
			"",
			"void solve() {",
			"    ",
			"}",
			"",
			"signed main() {",
			"    ios::sync_with_stdio(0);",
			"    cin.tie(0);",
			"    solve();",
			"    return 0;",
			"}"
		],
		"description": "C++ Template with common includes and macros"
	},
	"Sparse Table": {
		"scope": "cpp",
		"prefix": "sparse_table",
		"body": [
			"struct sparse_table {",
			"    vector<vector<int>> ST;",
			"    int N, K;",
			"",
			"    // Constructor to build the Sparse Table",
			"    sparse_table(int _N, const vector<int>& a) : N(_N) {",
			"        K = MSB(N);  // Find the maximum power of 2 <= N",
			"        ST.resize(K);",
			"        ST[0] = a;  // Initialize the first row of the Sparse Table with the input array",
			"",
			"        // Build the Sparse Table",
			"        for (int k = 1; k < K; ++k) {",
			"            ST[k].resize(N - (1 << k) + 1);  // Resize the kth row based on range size",
			"            for (int i = 0; i + (1 << k) <= N; ++i) {",
			"                ST[k][i] = gcd(ST[k-1][i], ST[k-1][i + (1 << (k-1))]);",
			"            }",
			"        }",
			"    }",
			"",
			"    // Returns most significant bit of an integer",
			"    inline int MSB(unsigned int x) { return 32 - __builtin_clz(x); }",
			"",
			"    // Query in the range [x, y]",
			"    int query(int x, int y) {",
			"        int k = MSB(y - x + 1) - 1;  // Find the highest power of 2 that fits in the range",
			"        return gcd(ST[k][x], ST[k][y - (1 << k) + 1]);",
			"    }",
			"};",
			""
		],
		"description": "Sparse Table"
	},
	"UnionFind": {
		"scope": "cpp",
		"prefix": "union_find",
		"body": [
			"class UnionFind {",
			"private:",
			"    vector<int> p, rank, setSize;",
			"    int numSets;",
			"public:",
			"    UnionFind(int N) {",
			"        p.assign(N, 0); for (int i = 0; i < N; ++i) p[i] = i;",
			"        rank.assign(N, 0);                           // optional speedup",
			"        setSize.assign(N, 1);                        // optional feature",
			"        numSets = N;                                 // optional feature",
			"    }",
			"",
			"    int find_set(int i) { return (p[i] == i) ? i : (p[i] = find_set(p[i])); }",
			"    bool is_same_set(int i, int j) { return find_set(i) == find_set(j); }",
			"",
			"    int num_disjoint() { return numSets; }      // optional",
			"    int size_of_set(int i) { return setSize[find_set(i)]; } // optional",
			"",
			"    void union_set(int i, int j) {",
			"        if (is_same_set(i, j)) return;                 // i and j are in same set",
			"        int x = find_set(i), y = find_set(j);          // find both rep items",
			"        if (rank[x] > rank[y]) swap(x, y);           // keep x 'shorter' than y",
			"        p[x] = y;                                    // set x under y",
			"        if (rank[x] == rank[y]) ++rank[y];           // optional speedup",
			"        setSize[y] += setSize[x];                    // combine set sizes at y",
			"        --numSets;                                   // a union reduces numSets",
			"    }",
			"};",
			"",
			"// UnionFind ufds (N);          // Create a UFDS with [0..N-1] items",
			"// ufds.find_set(i);            // returns which set i belongs to",
			"// ufds.is_same_set(i, j);      // returns bool 0/1 if i, j are in same set",
			"// ufds.union_set(i, j);        // combines set containing i and set containing j",
			"// ufds.num_disjoint();         // returns int, number of disjoint sets"
		],
		"description": "Union-Find Disjoint Set (UFDS)"
	},
    "Segment Tree": {
        "prefix": "segment_tree",
        "body": [
            "struct node {",
            "\tint s, e;",
            "\tll mn, mx, sum, xr;",
            "\tbool lset;",
            "\tll add_val, set_val;",
            "\tnode *l, *r;",
            "\tnode (int _s, int _e, const vector<int>& A = {}): s(_s), e(_e), mn(0), mx(0), sum(0), xr(0), lset(0), add_val(0), set_val(0), l(NULL), r(NULL) {",
            "\t\tif (A.empty()) return;",
            "\t\tif (s == e) mn = mx = sum = xr = A[s];",
            "\t\telse {",
            "\t\t\tl = new node(s, (s+e)>>1, A), r = new node((s+e+2)>>1, e, A);",
            "\t\t\tcombine();",
            "\t\t}",
            "\t}",
            "\tvoid create_children() {",
            "\t\tif (s == e) return;",
            "\t\tif (l != NULL) return;",
            "\t\tint m = (s+e)>>1;",
            "\t\tl = new node(s, m);",
            "\t\tr = new node(m+1, e);",
            "\t}",
            "\tvoid self_set(ll v) {",
            "\t\tlset = 1;",
            "\t\tmn = mx = set_val = v;",
            "\t\tsum = v * (e-s+1);",
            "\t\txr = v * (e-s+1);",
            "\t\tadd_val = 0;",
            "\t}",
            "\tvoid self_add(ll v) {",
            "\t\tif (lset) { self_set(v + set_val); return; }",
            "\t\tmn += v, mx += v, add_val += v;",
            "\t\tsum += v*(e-s+1);",
            "\t\txr ^= v * (e-s+1);",
            "\t}",
            "\tvoid lazy_propagate() {",
            "\t\tif (s == e) return;",
            "\t\tif (lset) {",
            "\t\t\tl->self_set(set_val), r->self_set(set_val);",
            "\t\t\tlset = set_val = 0;",
            "\t\t}   ",
            "\t\tif (add_val != 0) {",
            "\t\t\tl->self_add(add_val), r->self_add(add_val);",
            "\t\t\tadd_val = 0;",
            "\t\t}",
            "\t}",
            "\tvoid combine() {",
            "\t\tif (l == NULL) return;",
            "\t\tsum = l->sum + r->sum;",
            "\t\tmn = min(l->mn, r->mn);",
            "\t\tmx = max(l->mx, r->mx);",
            "\t\txr = l->xr ^ r->xr;",
            "\t}",
            "\tvoid add(int x, int y, ll v) {",
            "\t\tif (s == x && e == y) { self_add(v); return; }",
            "\t\tint m = (s+e)>>1;",
            "\t\tcreate_children(); lazy_propagate();",
            "\t\tif (x <= m) l->add(x, min(y, m), v);",
            "\t\tif (y > m) r->add(max(x, m+1), y, v);",
            "\t\tcombine();",
            "\t}",
            "\tvoid set(int x, int y, ll v) {",
            "\t\tif (s == x && e == y) { self_set(v); return; }",
            "\t\tint m = (s+e)>>1;",
            "\t\tcreate_children(); lazy_propagate();",
            "\t\tif (x <= m) l->set(x, min(y, m), v);",
            "\t\tif (y > m) r->set(max(x, m+1), y, v);",
            "\t\tcombine();",
            "\t}",
            "\tll range_sum(int x, int y) {",
            "\t\tif (s == x && e == y) return sum;",
            "\t\tif (l == NULL || lset) return (sum / (e-s+1)) * (y-x+1);",
            "\t\tint m = (s+e)>>1;",
            "\t\tlazy_propagate();",
            "\t\tif (y <= m) return l->range_sum(x, y);",
            "\t\tif (x > m) return r->range_sum(x, y);",
            "\t\treturn l->range_sum(x, m) + r->range_sum(m+1, y);",
            "\t}",
            "\tll range_min(int x, int y) {",
            "\t\tif (s == x && e == y) return mn;",
            "\t\tif (l == NULL || lset) return mn;",
            "\t\tint m = (s+e)>>1;",
            "\t\tlazy_propagate();",
            "\t\tif (y <= m) return l->range_min(x, y);",
            "\t\tif (x > m) return r->range_min(x, y);",
            "\t\treturn min(l->range_min(x, m), r->range_min(m+1, y));",
            "\t}",
            "\tll range_max(int x, int y) {",
            "\t\tif (s == x && e == y) return mx;",
            "\t\tif (l == NULL || lset) return mx;",
            "\t\tint m = (s+e)>>1;",
            "\t\tlazy_propagate();",
            "\t\tif (y <= m) return l->range_max(x, y);",
            "\t\tif (x > m) return r->range_max(x, y);",
            "\t\treturn max(l->range_max(x, m), r->range_max(m+1, y));",
            "\t}",
            "\tll range_xor(int x, int y) {",
            "\t\tif (s == x && e == y) return xr;",
            "\t\tif (l == NULL || lset) return xr;",
            "\t\tint m = (s+e)>>1;",
            "\t\tlazy_propagate();",
            "\t\tif (y <= m) return l->range_xor(x, y);",
            "\t\tif (x > m) return r->range_xor(x, y);",
            "\t\treturn l->range_xor(x, m) ^ r->range_xor(m+1, y);",
            "\t}",
            "\t~node() {",
            "\t\tif (l != NULL) delete l;",
            "\t\tif (r != NULL) delete r;",
            "\t}",
            "} *root;",
            "",
            "// root = new node(0, n - 1, A);       // Creates segment tree with range [0, n-1] wiht A",
            "// root = new node(0, 10000000000);    // Creates segment tree with range [0, 10000000000]",
            "// root->add(0, 3, 5);                 // Adds 5 to all elements in range [0, 3]",
            "// root->set(0, 3, 5);                 // Sets all elements in range [0, 3] to 5",
            "// root->range_sum(0, 3);               // Returns sum of elements in range [0, 3]"
        ],
        "description": "Segment Tree"
    },
    "Ordered Set": {
        "prefix": "pbds",
        "body": [
            "// PBDS",
            "// Sorted in ascending order of TYPE_T",
            "#include <bits/extc++.h>",
            "using namespace __gnu_pbds;",
            "typedef tree<TYPE_T, null_type, less<TYPE_T>, rb_tree_tag,",
            "    tree_order_statistics_node_update> ost;",
            "",
            "// Sorted in descending order of TYPE_T",
            "#include <bits/extc++.h>",
            "using namespace __gnu_pbds;",
            "typedef tree<TYPE_T, null_type, greater_equal<TYPE_T>,",
            "    rb_tree_tag, tree_order_statistics_node_update> ost;",
            "",
            "// Usage: TYPE_T -> pair<int, int>",
            "// ost rankings;                                     // Initialization",
            "// rankings.insert(x);                               // Inserting element x into the tree",
            "// int rank = rankings.order_of_key(x);              // Retrieving order of element x",
            "//                                                      x DOES NOT have to be in pbds",
            "// int idx = rankings.order_of_key(target);          // Erasing part 1",
            "// rankings.erase(rankings.find_by_order(idx));      // Erasing part 2",
            "//",
            "// rankings.insert({x, i + 1});                      // pbds with duplicate xs",
            "// int rank = rankings.order_of_key({y, 0})          // get top ranking of all elements of val y",
            ""
        ],
        "description": "Ordered Set"
    },
    "Fenwick Tree": {
        "prefix": "fenwicktree",
        "body": [
            "class FenwickTree {",
            "public:",
            "    int N;",
            "    vector<ll> fw, fw2;",
            "",
            "    FenwickTree(ll size) : N(size + 1), fw(N, 0), fw2(N, 0) {}",
            "",
            "    void update(int x, int y, ll v) { // inclusive",
            "        x++, y++; // Shift to 1-based indexing internally",
            "        for (int tx = x; tx < N; tx += tx & (-tx)) {",
            "            fw[tx] += v;",
            "            fw2[tx] -= v * (x - 1);",
            "        }",
            "        for (int ty = y + 1; ty < N; ty += ty & (-ty)) {",
            "            fw[ty] -= v;",
            "            fw2[ty] += v * y;",
            "        }",
            "    }",
            "",
            "    ll sum(int x) {",
            "        x++; // Shift to 1-based indexing internally",
            "        ll res = 0;",
            "        for (int tx = x; tx; tx -= tx & (-tx))",
            "            res += fw[tx] * x + fw2[tx];",
            "        return res;",
            "    }",
            "",
            "    ll range_sum(int x, int y) { // inclusive",
            "        return sum(y) - sum(x - 1);",
            "    }",
            "};",
            "// FenwickTree ft(n);               // Init a Fenwick Tree (0-indexed)",
            "// ll rs = ft.range_sum(p, q);      // Do a range_sum from [p, q] inclusive",
            "// ft.update(a, b, c)               // Add c to every element in [a, b] inclusive"
        ],
        "description": "Fenwick Tree"
    },
    "Max flow": {
        "prefix": "maxflow",
        "body": [
            "typedef tuple<int, ll, ll> edge;",
            "const ll INF = 1e18;",
            "/*",
            "Dinic implementation of maxflow.",
            "Time: O(min(mf, V^2)* E)",
            "*/",
            "class max_flow {",
            "    private:",
            "    int V;",
            "    vector<edge> EL;  // EL[i] = {dest node, capacity, flow (+ means u -> dest)}",
            "    vector<vi> AL;    // AL[u] = {EL indices of edges coming from u}",
            "    vi d, last;",
            "    vector<ii> p;",
            "",
            "    bool BFS(int s, int t) {  // find augmenting path",
            "        d.assign(V, -1);",
            "        d[s] = 0;",
            "        queue<int> q({s});",
            "        p.assign(V, {-1, -1});  // record BFS sp tree",
            "        while (!q.empty()) {",
            "            int u = q.front();",
            "            q.pop();",
            "            if (u == t) break;                         // stop as sink t reached",
            "            for (auto &idx : AL[u]) {                  // explore neighbors of u",
            "                auto &[v, cap, flow] = EL[idx];        // stored in EL[idx]",
            "                if ((cap - flow > 0) && (d[v] == -1))  // positive residual edge",
            "                    d[v] = d[u] + 1, q.push(v),",
            "                    p[v] = {u, idx};  // 3 lines in one!",
            "            }",
            "        }",
            "        return d[t] != -1;  // has an augmenting path",
            "    }",
            "",
            "    ll DFS(int u, int t, ll f = INF) {  // traverse from s->t",
            "        if ((u == t) || (f == 0)) return f;",
            "        for (int &i = last[u]; i < (int)AL[u].size(); ++i) {  // from last edge",
            "            auto &[v, cap, flow] = EL[AL[u][i]];",
            "            if (d[v] != d[u] + 1) continue;  // not part of layer graph",
            "            if (ll pushed = DFS(v, t, min(f, cap - flow))) {",
            "                flow += pushed;",
            "                auto &rflow = get<2>(EL[AL[u][i] ^ 1]);  // back edge",
            "                rflow -= pushed;",
            "                return pushed;",
            "            }",
            "        }",
            "        return 0;",
            "    }",
            "",
            "    public:",
            "    max_flow(int initialV) : V(initialV) {",
            "        EL.clear();",
            "        AL.assign(V, vi());",
            "    }",
            "",
            "    void clear() {",
            "        EL.clear();",
            "        AL.assign(V, vi());",
            "        d.clear();",
            "        last.clear();",
            "        p.clear();",
            "    }",
            "",
            "    // if you are adding a bidirectional edge u<->v with weight w into your",
            "    // flow graph, set directed = false (default value is directed = true)",
            "    void add_edge(int u, int v, ll w, bool directed = true) {",
            "        if (u == v) return;                       // safeguard: no self loop",
            "        EL.emplace_back(v, w, 0);                 // u->v, cap w, flow 0",
            "        AL[u].push_back(EL.size() - 1);           // remember this index",
            "        EL.emplace_back(u, directed ? 0 : w, 0);  // back edge",
            "        AL[v].push_back(EL.size() - 1);           // remember this index",
            "    }",
            "",
            "    ll dinic(int s, int t) {",
            "        ll mf = 0;                    // mf stands for max_flow",
            "        while (BFS(s, t)) {           // an O(V^2*E) algorithm",
            "            last.assign(V, 0);        // important speedup",
            "            while (ll f = DFS(s, t))  // exhaust blocking flow",
            "                mf += f;",
            "        }",
            "        return mf;",
            "    }",
            "",
            "    void debug_el() {",
            "        for (int u = 0; u < V; u++) {",
            "            for (auto v : AL[u]) {",
            "                auto [a, b, c] = EL[v];",
            "                cout << u _ a _ b _ c << endl;",
            "            }",
            "        }",
            "    }",
            "",
            "    set<int> get_s_mincut(int s, int t) {",
            "        // dinic(s, t);",
            "        vector<bool> visited(V, false);",
            "        set<int> s_component;",
            "        queue<int> q;",
            "        q.push(s);",
            "        visited[s] = true;",
            "        while (!q.empty()) {",
            "            int u = q.front();",
            "            q.pop();",
            "            s_component.insert(u);",
            "            for (auto &idx : AL[u]) {",
            "                auto &[v, cap, flow] = EL[idx];",
            "                if ((cap - flow > 0) && (!visited[v])) {",
            "                    visited[v] = true;",
            "                    q.push(v);",
            "                }",
            "            }",
            "        }",
            "        return s_component;",
            "    }",
            "};",
            "// max_flow mf(N);                  // Create maxflow object",
            "// mf.add_edge(u, v, w);            // Add a directed edge from u to v with",
            "// capacity w mf.add_edge(u, v, w, false)      // Add a undirected edge from u",
            "// to v with capacity w ll ans = mf.dinic(src, sink);    // Get the maxflow",
            ""
        ],
        "description": "Max flow"
    },
    "Min cost Max flow": {
        "prefix": "mincostmaxflow",
        "body": [
            "typedef tuple<int, ll, ll, ll> edge;",
            "const ll INF = 1e18;",
            "class min_cost_max_flow {",
            "    private:",
            "    int V;",
            "    ll total_cost;",
            "    vector < edge > EL;",
            "    vector < vi > AL;",
            "    vll d;",
            "    vi last,",
            "    vis;",
            "",
            "    bool SPFA(int s, int t) { // SPFA to find augmenting path in residual graph",
            "        d.assign(V, INF);",
            "        d[s] = 0;",
            "        vis[s] = 1;",
            "        queue < int > q({",
            "            s",
            "        });",
            "        while (!q.empty()) {",
            "            int u = q.front();",
            "            q.pop();",
            "            vis[u] = 0;",
            "            for (auto & idx: AL[u]) { // explore neighbors of u",
            "                auto & [v, cap, flow, cost] = EL[idx]; // stored in EL[idx]",
            "                if ((cap - flow > 0) && (d[v] > d[u] + cost)) { // positive residual edge",
            "                    d[v] = d[u] + cost;",
            "                    if (!vis[v]) q.push(v), vis[v] = 1;",
            "                }",
            "            }",
            "        }",
            "        return d[t] != INF; // has an augmenting path",
            "    }",
            "",
            "    ll DFS(int u, int t, ll f = INF) { // traverse from s->t",
            "        if ((u == t) || (f == 0)) return f;",
            "        vis[u] = 1;",
            "        for (int & i = last[u]; i < (int) AL[u].size(); ++i) { // from last edge",
            "            auto & [v, cap, flow, cost] = EL[AL[u][i]];",
            "            if (!vis[v] && d[v] == d[u] + cost) { // in current layer graph",
            "                if (ll pushed = DFS(v, t, min(f, cap - flow))) {",
            "                    total_cost += pushed * cost;",
            "                    flow += pushed;",
            "                    auto & [rv, rcap, rflow, rcost] = EL[AL[u][i] ^ 1]; // back edge",
            "                    rflow -= pushed;",
            "                    vis[u] = 0;",
            "                    return pushed;",
            "                }",
            "            }",
            "        }",
            "        vis[u] = 0;",
            "        return 0;",
            "    }",
            "",
            "    public: ",
            "    min_cost_max_flow(int initialV): V(initialV), total_cost(0) {",
            "        EL.clear();",
            "        AL.assign(V, vi());",
            "        vis.assign(V, 0);",
            "    }",
            "",
            "    // if you are adding a bidirectional edge u<->v with weight w into your",
            "    // flow graph, set directed = false (default value is directed = true)",
            "    void add_edge(int u, int v, ll w, ll c, bool directed = true) {",
            "        if (u == v) return; // safeguard: no self loop",
            "        EL.emplace_back(v, w, 0, c); // u->v, cap w, flow 0, cost c",
            "        AL[u].push_back(EL.size() - 1); // remember this index",
            "        EL.emplace_back(u, 0, 0, -c); // back edge",
            "        AL[v].push_back(EL.size() - 1); // remember this index",
            "        if (!directed) add_edge(v, u, w, c); // add again in reverse",
            "    }",
            "",
            "    pair < ll, ll > mcmf(int s, int t) {",
            "        ll mf = 0; // mf stands for max_flow",
            "        while (SPFA(s, t)) { // an O(V^2*E) algorithm",
            "            last.assign(V, 0); // important speedup",
            "            while (ll f = DFS(s, t)) // exhaust blocking flow",
            "                mf += f;",
            "        }",
            "        return {",
            "            mf,",
            "            total_cost",
            "        };",
            "    }",
            "};",
            "// min_cost_max_flow mf(v);",
            "// mf.add_edge(u, v, w, c);",
            "// llp res = mf.mcmf(s, t);",
            ""
        ],
        "description": "Min cost Max flow"
    },
    "Min cost Max flow (Double)": {
        "prefix": "mincostmaxflow_double",
        "body": [
            "",
            "typedef tuple<int, ll, ll, double> edge;    // node, capacity, flow, cost",
            "const ll INF = 1e18;",
            "const double INFD = 1e9;",
            "double eps = 1e-7;",
            "class min_cost_max_flow {",
            "    private:",
            "    int V;",
            "    double total_cost;",
            "    vector < edge > EL;",
            "    vector < vi > AL;",
            "    vector<double> d;",
            "    vi last, vis;",
            "",
            "    bool SPFA(int s, int t) { // SPFA to find augmenting path in residual graph",
            "        d.assign(V, INFD);",
            "        d[s] = 0;",
            "        vis[s] = 1;",
            "        queue < int > q({s});",
            "        while (!q.empty()) {",
            "            int u = q.front();",
            "            q.pop();",
            "            vis[u] = 0;",
            "            for (auto & idx: AL[u]) { // explore neighbors of u",
            "                auto & [v, cap, flow, cost] = EL[idx]; // stored in EL[idx]",
            "                if ((cap - flow > 0) && (d[v] > d[u] + cost)) { // positive residual edge",
            "                    d[v] = d[u] + cost;",
            "                    if (!vis[v]) q.push(v), vis[v] = 1;",
            "                }",
            "            }",
            "        }",
            "        // return d[t] != INF; // has an augmenting path",
            "        return d[t] != INFD;",
            "    }",
            "",
            "    ll DFS(int u, int t, ll f = INF) { // traverse from s->t'",
            "        if ((u == t) || (f == 0)) return f;",
            "        vis[u] = 1;",
            "        for (int & i = last[u]; i < (int) AL[u].size(); ++i) { // from last edge",
            "            auto & [v, cap, flow, cost] = EL[AL[u][i]];",
            "            if (!vis[v] && d[v] - d[u] - cost < eps) { // in current layer graph",
            "                if (ll pushed = DFS(v, t, min(f, cap - flow))) {",
            "                    total_cost += pushed * cost;",
            "                    flow += pushed;",
            "                    auto & [rv, rcap, rflow, rcost] = EL[AL[u][i] ^ 1]; // back edge",
            "                    rflow -= pushed;",
            "                    vis[u] = 0;",
            "                    return pushed;",
            "                }",
            "            }",
            "        }",
            "        vis[u] = 0;",
            "        return 0;",
            "    }",
            "",
            "    public: ",
            "    min_cost_max_flow(int initialV): V(initialV), total_cost(0) {",
            "        EL.clear();",
            "        AL.assign(V, vi());",
            "        vis.assign(V, 0);",
            "    }",
            "",
            "    // if you are adding a bidirectional edge u<->v with weight w into your",
            "    // flow graph, set directed = false (default value is directed = true)",
            "    void add_edge(int u, int v, ll w, double c, bool directed = true) {",
            "        if (u == v) return; // safeguard: no self loop",
            "        EL.emplace_back(v, w, 0, c); // u->v, cap w, flow 0, cost c",
            "        AL[u].push_back(EL.size() - 1); // remember this index",
            "        EL.emplace_back(u, 0, 0, -c); // back edge",
            "        AL[v].push_back(EL.size() - 1); // remember this index",
            "        if (!directed) add_edge(v, u, w, c); // add again in reverse",
            "    }",
            "",
            "    pair <ll, double> mcmf(int s, int t) {",
            "        ll mf = 0; // mf stands for max_flow",
            "        while (SPFA(s, t)) { // an O(V^2*E) algorithm",
            "            last.assign(V, 0); // important speedup",
            "            while (ll f = DFS(s, t)) // exhaust blocking flow",
            "                mf += f;",
            "        }",
            "        return {mf, total_cost};",
            "    }",
            "};",
            "// min_cost_max_flow mf(v);",
            "// mf.add_edge(u, v, w, c);"
        ],
        "description": "Min cost Max flow (Double)"
    },
    "Hungarian": {
        "prefix": "hungarian",
        "body": [
            "const ll INF = 1e18;",
            "/*",
            "Hungarian algorithm",
            "",
            "Given a weighted bipartite graph, match every node on the left with a node on the right s.t. ",
            "no nodes are in two matchings and sum of edge weights is **minimal**.",
            "",
            "Takes cost[n][m], where cost[i][j] = cost for L[i] to be matched with R[j] and n < m.",
            "returns {min_cost, match} where L[i] is matched with R[match[i]].",
            "",
            "Time: O(N^2 x M)",
            "*/",
            "pair<ll, vi> hungarian(const vector<vll> &a) {",
            "    if (a.empty()) return {0, {}};",
            "    int n = a.size() + 1, m = a[0].size() + 1;",
            "    vll u(n), v(m);",
            "    vi p(m), ans(n - 1);",
            "    for (int i = 1; i < n; i++) {",
            "        p[0] = i;",
            "        int j0 = 0; // add \"dummy\" worker 0",
            "        vll dist(m, INF);",
            "        vi pre(m, -1);",
            "        vector<bool> done(m + 1);",
            "        do { // Dijkstra",
            "            done[j0] = true;",
            "            int i0 = p[j0], j1;",
            "            ll delta = INF;",
            "            for (int j = 1; j < m; j++) ",
            "                if (!done[j]) {",
            "                    auto cur = a[i0 - 1][j - 1] - u[i0] - v[j];",
            "                    if (cur < dist[j]) dist[j] = cur, pre[j] = j0;",
            "                    if (dist[j] < delta) delta = dist[j], j1 = j;",
            "                }",
            "            for (int j = 0; j < m; j++) {",
            "                if (done[j]) u[p[j]] += delta, v[j] -= delta;",
            "                else dist[j] -= delta;",
            "            }",
            "            j0 = j1;",
            "        } while (p[j0]);",
            "        while (j0) { // update alternating path",
            "            int j1 = pre[j0];",
            "            p[j0] = p[j1], j0 = j1;",
            "        }",
            "    }",
            "    for (int j = 1; j < m; j++) if (p[j]) ans[p[j] - 1] = j - 1;",
            "    return {-v[0], ans}; // min cost",
            "}",
            ""
        ],
        "description": "Weighted MCBM"
    },
    "Dijkstra": {
        "prefix": "dijkstra",
        "body": [
            "const ll INF = 1e18;",
            "vll dijkstra(int src, vector<vii>& adj) {",
            "    int n = adj.size();",
            "    vll dist(n, INF);",
            "    min_heap<pair<ll, int>> pq;",
            "    dist[src] = 0;",
            "    pq.push({0, src});",
            "    while (!pq.empty()) {",
            "        auto [d, u] = pq.top(); pq.pop();",
            "        if (d > dist[u]) continue;",
            "        ",
            "        for (auto [v, w] : adj[u]) {",
            "            if (dist[u] + w < dist[v]) {",
            "                dist[v] = dist[u] + w;",
            "                pq.push({dist[v], v});",
            "            }",
            "        }",
            "    }",
            "    return dist;",
            "}"
        ],
        "description": "Dijkstra"
    },
    "Floor sqrt": {
        "prefix": "squareroot",
        "body": [
            "ll int_sqrt (ll x) {",
            "    ll ans = 0;",
            "    for (ll k = 1LL << 30; k != 0; k /= 2) {",
            "        if ((ans + k) * (ans + k) <= x) {",
            "            ans += k;",
            "        }",
            "    }",
            "    return ans;",
            "}"
        ],
        "description": "Floor sqrt"
    },
    "Combinatorics": {
        "prefix": "pnc",
        "body": [
            "const ll MAX_N = 5e5 + 5;",
            "const ll p = 998244353;",
            "",
            "ll mod(ll a, ll m) { return ((a % m) + m) % m;}",
            "",
            "ll modPow(ll b, ll p, ll m) {",
            "    ll res = 1;",
            "    while (p) {",
            "        if (p&1) res = (res * b) % m;",
            "        p>>=1;",
            "        b = (b * b) % m;",
            "    }",
            "    return res;",
            "}",
            "",
            "ll inv(ll a) {return modPow(a, p - 2, p);}",
            "",
            "vll fact;",
            "// fact.assign(MAX_N + 1, 0);",
            "// fact[0] = 1;",
            "// for (int i = 1; i < MAX_N; i++)",
            "//     fact[i] = (fact[i - 1] * i) % p;"
        ],
        "description": "Combinatorics"
    },
    "Binary Print": {
        "prefix": "binaryprint",
        "body": [
            "string bprint(ll x) {",
            "    if (x <= 1) return to_string(x);",
            "    string res = \"\";",
            "    for (int i = __lg(x); i >= 0; i--) {",
            "        res += ((x>>i) & 1) ? '1' : '0';",
            "    }",
            "    return res;",
            "}"
        ],
        "description": "Binary Print"
    },
    "Range Minimum Query": {
        "prefix": "rmq",
        "body": [
            "class SparseTable {                              // OOP style",
            "private:",
            "    vi A, P2, L2;",
            "    vector<vi> SpT;                                // the Sparse Table",
            "public:",
            "    SparseTable() {}                               // default constructor",
            "    ",
            "    SparseTable(vi &initialA) {                    // pre-processing routine",
            "        A = initialA;",
            "        int n = (int)A.size();",
            "        int L2_n = (int)log2(n)+1;",
            "        P2.assign(L2_n+1, 0);",
            "        L2.assign((1<<L2_n)+1, 0);",
            "        for (int i = 0; i <= L2_n; ++i) {",
            "            P2[i] = (1<<i);                            // to speed up 2^i",
            "            L2[(1<<i)] = i;                            // to speed up log_2(i)",
            "        }",
            "        for (int i = 2; i < P2[L2_n]; ++i)",
            "            if (L2[i] == 0)",
            "                L2[i] = L2[i-1];                         // to fill in the blanks",
            "    ",
            "        // the initialization phase",
            "        SpT = vector<vi>(L2[n]+1, vi(n));",
            "        for (int j = 0; j < n; ++j)",
            "            SpT[0][j] = j;                             // rmq of sub array [j..j]",
            "    ",
            "        // the two nested loops below have overall time complexity = O(n log n)",
            "        for (int i = 1; P2[i] <= n; ++i) {             // for all i s.t. 2^i <= n",
            "            for (int j = 0; j+P2[i]-1 < n; ++j) {      // for all valid j",
            "                int x = SpT[i-1][j];                     // [j..j+2^(i-1)-1]",
            "                int y = SpT[i-1][j+P2[i-1]];             // [j+2^(i-1)..j+2^i-1]",
            "                SpT[i][j] = A[x] <= A[y] ? x : y;",
            "            }",
            "        }",
            "    }",
            "    ",
            "    // returns index of minimum value",
            "    int rmq(int i, int j) {",
            "        int k = L2[j-i+1];                           // 2^k <= (j-i+1)",
            "        int x = SpT[k][i];                           // covers [i..i+2^k-1]",
            "        int y = SpT[k][j-P2[k]+1];                   // covers [j-2^k+1..j]",
            "        return A[x] <= A[y] ? x : y;",
            "    }",
            "};",
            "// SparseTable st(L);               // Init",
            "// int idx = st.rmq(l, r);          // Get index of minimum value"
        ],
        "description": "Range Minimum Query"
    },
    "Lowest Common Ancestor": {
        "prefix": "lca",
        "body": [
            "vi E;   // Sequence of nodes in dfs",
            "vi L;   // Depth of node in E[i]",
            "vi H;   // H[i] is the first occurence of i in H",
            "int idx;",
            "",
            "void dfs(int u, int depth, vvi& adj, vi& visited) {",
            "    visited[u] = 1;",
            "    H[u] = idx;",
            "    E[idx] = u;",
            "    L[idx] = depth;",
            "    idx++;",
            "",
            "    for (int v : adj[u]) {",
            "        if (visited[v]) continue;",
            "        dfs(v, depth + 1, adj, visited);",
            "        E[idx] = u;",
            "        L[idx] = depth;",
            "        idx++;",
            "    }",
            "}",
            "// idx = 0;",
            "// L.assign(2*n, -1);",
            "// E.assign(2*n, -1);",
            "// H.assign(n, -1);",
            "// vi visited(n, 0);",
            "// dfs(0, 0, adj, visited);",
            "",
            "// SparseTable st(L);",
            "",
            "// auto lca = [&st] (int u, int v) {",
            "//     return E[st.rmq(min(H[u], H[v]), max(H[u], H[v]))];",
            "// };"
        ],
        "description": "Lowest Common Ancestor"
    },
    "Prime Counting": {
        "prefix": "prime_count",
        "body": [
            "/***",
            " *",
            " * Prime counting function in sublinear time with the Meissel-Lehmer algorithm",
            " *",
            " * The function lehmer(n) returns the number of primes not exceeding n",
            " * Complexity: Roughly ~O(n^(2/3))",
            " *",
            "***/",
            "/// Magic constants, optimized to answer prime counting queries for n=10^12 but can be tweaked",
            "const int MAXV = 20000010;",
            "const int MAXP = 7;",
            "const int MAXN = 50;",
            "const int MAXM = 2 * 3 * 7 * 5 * 11 * 13 * 17; /// Product of the first MAXP primes",
            "",
            "constexpr auto fast_div = [](const long long& a, const int& b) ->long long {return double(a) / b + 1e-9;};",
            "",
            "vector<int> primes;",
            "bitset<MAXV> is_prime;",
            "int prod[MAXP], pi[MAXV], dp[MAXN][MAXM];",
            "",
            "void sieve(){",
            "    is_prime[2] = true;",
            "    for (int i = 3; i < MAXV; i += 2) is_prime[i] = true;",
            "",
            "    for (int i = 3; i * i < MAXV; i += 2){",
            "        for (int j = i * i; is_prime[i] && j < MAXV; j += (i << 1)){",
            "            is_prime[j] = false;",
            "        }",
            "    }",
            "",
            "    for (int i = 1; i < MAXV; i++){",
            "        pi[i] = pi[i - 1] + is_prime[i];",
            "        if (is_prime[i]) primes.push_back(i);",
            "    }",
            "}",
            "",
            "void gen(){",
            "    int i, j;",
            "    assert(MAXN >= MAXP);",
            "",
            "    sieve();",
            "    for (prod[0] = primes[0], i = 1; i < MAXP; i++){",
            "        prod[i] = prod[i - 1] * primes[i];",
            "    }",
            "",
            "    for (i = 0; i < MAXM; i++) dp[0][i] = i;",
            "    for (i = 1; i < MAXN; i++){",
            "        for (j = 1; j < MAXM; j++){",
            "            dp[i][j] = dp[i - 1][j] - dp[i - 1][fast_div(j, primes[i - 1])];",
            "        }",
            "    }",
            "}",
            "",
            "ll phi(long long m, int n){",
            "    if (!n) return m;",
            "    if (n < MAXN && m < MAXM) return dp[n][m];",
            "    if (n < MAXP) return dp[n][m % prod[n - 1]] + fast_div(m, prod[n - 1]) * dp[n][prod[n - 1]];",
            "",
            "    long long p = primes[n - 1];",
            "    if (m < MAXV && p * p >= m) return pi[m] - n + 1;",
            "    if (p * p * p < m || m >= MAXV) return phi(m, n - 1) - phi(fast_div(m, p), n - 1);",
            "",
            "    int lim = pi[(int)sqrt(0.5 + m)];",
            "    ll res = pi[m] - (lim + n - 2) * (lim - n + 1) / 2;",
            "    for (int i = n; i < lim; i++){",
            "        res += pi[fast_div(m, primes[i])];",
            "    }",
            "",
            "    return res;",
            "}",
            "",
            "ll lehmer(long long n){",
            "    if (n < MAXV) return pi[n];",
            "",
            "    int s = sqrt(0.5 + n), c = cbrt(0.5 + n);",
            "    ll res = phi(n, pi[c]) + pi[c] - 1;",
            "    for (int i = pi[c]; i < pi[s]; i++){",
            "        res -= lehmer(fast_div(n, primes[i])) - i;",
            "    }",
            "",
            "    return res;",
            "}",
            "// gen();",
            "// ll ans = lehmer(n);      // number of primes <= x"
        ],
        "description": "Prime Counting"
    },
    "Factorization": {
        "prefix": "factorization",
        "body": [
            "using ull = unsigned long long;",
            "",
            "ull modmul(ull a, ull b, ull M) {",
            "    ll ret = a * b - M * ull(1.L / M * a * b);",
            "    return ret + M * (ret < 0) - M * (ret >= (ll)M);",
            "}",
            "",
            "ull modpow(ull b, ull e, ull mod) {",
            "    ull ans = 1;",
            "    for (; e; b = modmul(b, b, mod), e /= 2)",
            "        if (e & 1) ans = modmul(ans, b, mod);",
            "    return ans;",
            "}",
            "",
            "bool is_prime(ull n) {",
            "    if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;",
            "    ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},",
            "        s = __builtin_ctzll(n - 1), d = n >> s;",
            "    for (ull a : A) {  // ^ count trailing zeroes",
            "        ull p = modpow(a % n, d, n), i = s;",
            "        while (p != 1 && p != n - 1 && a % n && i--) p = modmul(p, p, n);",
            "        if (p != n - 1 && i != s) return 0;",
            "    }",
            "    return 1;",
            "}",
            "",
            "ull pollard(ull n) {",
            "    ull x = 0, y = 0, t = 30, prd = 2, i = 1, q;",
            "    auto f = [&](ull x) { return modmul(x, x, n) + i; };",
            "    while (t++ % 40 || __gcd(prd, n) == 1) {",
            "        if (x == y) x = ++i, y = f(x);",
            "        if ((q = modmul(prd, max(x, y) - min(x, y), n))) prd = q;",
            "        x = f(x), y = f(f(y));",
            "    }",
            "    return __gcd(prd, n);",
            "}",
            "",
            "vector<ull> factor(ull n) {",
            "    if (n == 1) return {};",
            "    if (is_prime(n)) return {n};",
            "    ull x = pollard(n);",
            "    auto l = factor(x), r = factor(n / x);",
            "    l.insert(l.end(), r.begin(), r.end());",
            "    return l;",
            "}",
            "",
            "// bool x_is_prime = is_prime(x);",
            "// vector<ull> x_factors = factor(x);"
        ],
        "description": "Factorization"
    },
    "String Hashing": {
        "prefix": "stringhash",
        "body": [
            "typedef uint64_t ull;",
            "static int C; // initialized below",
            "",
            "// Arithmetic mod two primes and 2^32 simultaneously.",
            "// \"typedef uint64_t H;\" instead if Thue-Morse does not apply.",
            "template<int M, class B>",
            "struct A {",
            "    int x; B b; A(int x=0) : x(x), b(x) {}",
            "    A(int x, B b) : x(x), b(b) {}",
            "    A operator+(A o){int y = x+o.x; return{y - (y>=M)*M, b+o.b};}",
            "    A operator-(A o){int y = x-o.x; return{y + (y< 0)*M, b-o.b};}",
            "    A operator*(A o) { return {(int)(1LL*x*o.x % M), b*o.b}; }",
            "    explicit operator ull() { return x ^ (ull) b << 21; }",
            "    bool operator==(A o) const { return (ull)*this == (ull)o; }",
            "    bool operator<(A o) const { return (ull)*this < (ull)o; }",
            "};",
            "typedef A<1000000007, A<1000000009, unsigned>> H;",
            "",
            "struct HashInterval {",
            "    vector<H> ha, pw;",
            "    HashInterval(string& str) : ha(sz(str) + 1), pw(ha) {",
            "        pw[0] = 1;",
            "        for (int i = 0; i < sz(str); i++)",
            "            ha[i+1] = ha[i] * C + str[i],",
            "            pw[i+1] = pw[i] * C;",
            "    }",
            "    H get_hash(int a, int b) { // hash [a, b)",
            "        return ha[b] - ha[a] * pw[b - a];",
            "    }",
            "};",
            "",
            "vector<H> get_hashes(string& str, int length) {",
            "    if (sz(str) < length) return {};",
            "    H h = 0, pw = 1;",
            "    for (int i = 0; i < length; i++)",
            "        h = h * C + str[i], pw = pw * C;",
            "    vector<H> ret = {h};",
            "    for (int i = length; i < sz(str); i++) {",
            "        ret.push_back(h = h * C + str[i] - pw * str[i-length]);",
            "    }",
            "    return ret;",
            "}",
            "#include<sys/time.h>",
            "// in main():",
            "//      timeval tp;",
            "//      gettimeofday(&tp, 0);",
            "//      C = (int)tp.tv_usec; // (less than modulo)",
            "",
            "// HashInterval hi(s);                       // Hash object of string s",
            "// ull h = (ull)hi.get_hash(a, b);           // Get hash of substring s[a, b)",
            "// auto hs = get_hashes(s, l);               // Get vector of hashes of length l for s"
        ],
        "description": "String Hashing"
    },
    "Suffix Array": {
        "prefix": "suffix_array",
        "body": [
            "struct SuffixArray {",
            "    vi sa, lcp;",
            "    string smem;",
            "    SuffixArray(string s, int lim=256) { // or vector<int>",
            "        smem = s;",
            "        s.push_back(0); int n = sz(s), k = 0, a, b;",
            "        vi x(all(s)), y(n), ws(max(n, lim));",
            "        sa = lcp = y, iota(all(sa), 0);",
            "        for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {",
            "            p = j, iota(all(y), n - j);",
            "            rep(i,0,n) if (sa[i] >= j) y[p++] = sa[i] - j;",
            "            fill(all(ws), 0);",
            "            rep(i,0,n) ws[x[i]]++;",
            "            rep(i,1,lim) ws[i] += ws[i - 1];",
            "            for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];",
            "            swap(x, y), p = 1, x[sa[0]] = 0;",
            "            rep(i,1,n) a = sa[i - 1], b = sa[i], x[b] =",
            "                (y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;",
            "        }",
            "        for (int i = 0, j; i < n - 1; lcp[x[i++]] = k)",
            "            for (k && k--, j = sa[x[i] - 1];",
            "                    s[i + k] == s[j + k]; k++);",
            "    }",
            "    void view() {",
            "        cerr << \" sa   lcp   suffix\" << '\\n';",
            "        int n = sz(smem);",
            "        for (int i = 0; i < n + 1; i++) {",
            "            cerr << std::setw(3) << sa[i];",
            "            cerr << std::setw(6) << lcp[i] << \"   \";",
            "            cerr << smem.substr(sa[i], n - sa[i]) << \"$\" << '\\n';",
            "        }",
            "    }",
            "};",
            "// SuffixArray sa(s)\t\t// Construct suffix array for string s",
            "// int x = sa.lcp[i];       // gives lcp(sa[i], sa[i-1]) for [1, n]",
            "// sa.view();\t\t\t\t// View suffix array structure"
        ],
        "description": "Suffix Array"
    }
}