CP.code-snippets

{
    "CP Template": {
		"prefix": "Reset",
		"body": [
		  "#include <bits/stdc++.h>",
		  "",
		  "using namespace std;",
		  "",
		  "#define fixed(n) fixed << setprecision(n)",
		  "#define ceil(n, m) (((n) + (m) - 1) / (m))",
		  "#define add_mod(a, b, m) (((a % m) + (b % m)) % m)",
		  "#define sub_mod(a, b, m) (((a % m) - (b % m) + m) % m)",
		  "#define mul_mod(a, b, m) (((a % m) * (b % m)) % m)",
		  "#define all(vec) vec.begin(), vec.end()",
		  "#define rall(vec) vec.rbegin(), vec.rend()",
		  "#define sz(x) int(x.size())",
		  "#define debug(x) cout << #x << \": \" << (x) << \"\\n\";",
		  "#define fi first",
		  "#define se second",
		  "#define ll long long",
		  "#define ull unsigned long long",
		  "#define EPS 1e-9",
		  "constexpr int INF = 1 << 30, Mod = 1e9 + 7;",
		  "constexpr ll LINF = 1LL << 62;",
		  "#define PI acos(-1)",
		  "template < typename T = int > using Pair = pair < T, T >;",
		  "vector < string > RET = {\"NO\", \"YES\"};",
		  "",
		  "template < typename T = int > istream& operator >> (istream &in, vector < T > &v) {",
		  "    for (auto &x : v) in >> x;",
		  "    return in;",
		  "}",
		  "",
		  "template < typename T = int > ostream& operator << (ostream &out, const vector < T > &v) { ",
		  "    for (const T &x : v) out << x << ' '; ",
		  "    return out;",
		  "}",
		  "",
		  "void Solve(){",
		  "    $1",
		  "}",
		  "",
		  "int main(){",
		  "    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);",
		  "    int test_cases = 1;",
		  "    // cin >> test_cases;",
		  "    for(int tc = 1; tc <= test_cases; tc++){",
		  "        // cout << \"Case #\" << tc << \": \";",
		  "        Solve();",
		  "    }",
		  "    return 0;",
		  "}"
		],
		"description": "CP Template"
	},
    "Binary Search Tree Structure": {
		"prefix": "BST",
		"body": [
		  "struct BST {",
		  "",
		  "    int data;",
		  "    BST *left, *right;",
		  "",
		  "    BST(int data = 0){",
		  "        this -> data = data;",
		  "        left = right = nullptr;",
		  "    }",
		  "",
		  "    // Insert New node",
		  "",
		  "    BST* Insert(BST* root, int val){",
		  "        if(!root) return new BST(val);",
		  "        if(val > root -> data)",
		  "            root -> right = Insert(root -> right, val);",
		  "        else",
		  "            root -> left = Insert(root -> left, val);",
		  "        return root;",
		  "    }",
		  "",
		  "    // Inorder Traverse (LRR)",
		  "",
		  "    void Inorder(BST* root){",
		  "        if(!root) return;",
		  "        Inorder(root -> left);",
		  "        cout << root -> data << \" \";",
		  "        Inorder(root -> right);",
		  "    }",
		  "",
		  "    // Preorde Traverse (RLR)",
		  "",
		  "    void Preorder(BST* root){",
		  "        if(!root) return;",
		  "        cout << root -> data << \" \";",
		  "        Preorder(root -> left);",
		  "        Preorder(root -> right);",
		  "    }",
		  "",
		  "    // Postorder Traverse (LRR)",
		  "",
		  "    void Postorder(BST* root){",
		  "        if(!root) return;",
		  "        Postorder(root -> left);",
		  "        Postorder(root -> right);",
		  "        cout << root -> data << \" \";",
		  "",
		  "    }",
		  "",
		  "    // Traverse each level",
		  "",
		  "    void Level_Order(BST* root){",
		  "        if(!root) return;",
		  "        queue < BST* > bfs;",
		  "        bfs.push(root);",
		  "        while(!bfs.empty()){",
		  "            BST* curr = bfs.front();",
		  "            bfs.pop();",
		  "            cout << curr -> data << \" \";",
		  "            if(curr -> left)",
		  "                bfs.push(curr -> left);",
		  "            if(curr -> right)",
		  "                bfs.push(curr -> right);",
		  "        }",
		  "    }",
		  "",
		  "    // Search on a node",
		  "",
		  "    bool Search(BST* root, int val){",
		  "        if(!root) return false;",
		  "        if(root -> data == val) return true;",
		  "        if(val > root -> data) return Search(root -> right, val);",
		  "        else return Search(root -> left, val);",
		  "    }",
		  "",
		  "    // Get minimum node in BST",
		  "",
		  "    BST* minValueNode(BST* node){",
		  "        BST* current = node;",
		  "        while (current && current -> left != nullptr) current = current -> left;",
		  "        return current;",
		  "    }",
		  "",
		  "    // Get maximum node in BST",
		  "",
		  "    BST* maxValueNode(BST* node){",
		  "        BST* current = node;",
		  "        while (current && current -> right != nullptr) current = current -> right;",
		  "        return current;",
		  "    }",
		  "",
		  "    // Delete Node",
		  "",
		  "    BST* Delete_Node(BST* root, int key){",
		  "        if(!root) return root;",
		  "        if(key < root -> data)",
		  "            root -> left = Delete_Node(root -> left, key);",
		  "        else if(key > root -> data)",
		  "            root -> right = Delete_Node(root -> right, key);",
		  "        else {",
		  "            if(!root -> left && !root -> right) return nullptr;",
		  "            else if(!root -> left){",
		  "                BST* temp = root -> right;",
		  "                free(root);",
		  "                return temp;",
		  "            }else if(!root -> right){",
		  "                BST* temp = root -> left;",
		  "                free(root);",
		  "                return temp;",
		  "            }",
		  "            BST* temp = minValueNode(root -> right);",
		  "            root -> data = temp -> data;",
		  "            root -> right = Delete_Node(root -> right, temp -> data);",
		  "        }",
		  "        return root;",
		  "    }",
		  "};"
		],
		"description": "Binary Search Tree Structure"
	},
    "Big Int Structure": {
		"prefix": "BigInt",
		"body": [
		  "struct BigInt {",
		  "",
		  "    const int BASE = 1000000000;",
		  "    vector < int > v;",
		  "    ",
		  "    BigInt() {}",
		  "",
		  "    BigInt(const long long &val) {",
		  "        *this = val;",
		  "    }",
		  "    ",
		  "    BigInt(const string &val) {",
		  "        *this = val;",
		  "    ",
		  "    }",
		  "    ",
		  "    int size() const { return v.size(); }",
		  "    ",
		  "    bool zero() const { return v.empty(); }",
		  "    ",
		  "    BigInt& operator = (long long val) {",
		  "        v.clear();",
		  "        while (val) {",
		  "            v.push_back(val % BASE);",
		  "            val /= BASE;",
		  "        }",
		  "        return *this;",
		  "    }",
		  "",
		  "    BigInt& operator = (const BigInt &a) {",
		  "        v = a.v;",
		  "        return *this;",
		  "    }",
		  "",
		  "    BigInt& operator = (const vector < int > &a) {",
		  "        v = a;",
		  "        return *this;",
		  "    }",
		  "",
		  "    BigInt& operator = (const string &s) {",
		  "        *this = 0;",
		  "        for (const char &ch : s)",
		  "            *this = *this * 10 + (ch - '0');",
		  "        return *this;",
		  "    }",
		  "    ",
		  "    bool operator < (const BigInt &a) const {",
		  "        if (a.size() != size())",
		  "            return size() < a.size();",
		  "        for (int i = size() - 1; i >= 0; i--)",
		  "            if (v[i] != a.v[i])",
		  "                return v[i] < a.v[i];",
		  "        return false;",
		  "    }",
		  "",
		  "    bool operator > (const BigInt &a) const {",
		  "        return a < *this;",
		  "    }",
		  "",
		  "    bool operator == (const BigInt &a) const {",
		  "        return (!(*this < a) && !(a < *this));",
		  "    }",
		  "",
		  "    bool operator <= (const BigInt &a) const {",
		  "        return ((*this < a) || !(a < *this));",
		  "    }",
		  "    ",
		  "    ll val(){",
		  "        ll ans = 0;",
		  "        for (int i = 0; i < size(); i++)",
		  "            ans = ans * 10 + v[i];",
		  "        return ans;",
		  "    }",
		  "",
		  "    BigInt operator + (const BigInt &a) const {",
		  "        BigInt res = *this;",
		  "        int idx = 0, carry = 0;",
		  "        while (idx < a.size() || carry) {",
		  "            if (idx < a.size())",
		  "                carry += a.v[idx];",
		  "            if (idx == res.size())",
		  "                res.v.push_back(0);",
		  "            res.v[idx] += carry;",
		  "            carry = res.v[idx] / BASE;",
		  "            res.v[idx] %= BASE;",
		  "            idx++;",
		  "        }",
		  "        return res;",
		  "    }",
		  "    ",
		  "    BigInt& operator += (const BigInt &a) {",
		  "        *this = *this + a;",
		  "        return *this;",
		  "    }",
		  "    ",
		  "    BigInt operator * (const BigInt &a) const {",
		  "        BigInt res;",
		  "        if (this -> zero() || a.zero())",
		  "            return res;",
		  "        res.v.resize(size() + a.size());",
		  "        for (int i = 0; i < size(); i++) {",
		  "            if (v[i] == 0)",
		  "                continue;",
		  "            long long carry = 0;",
		  "            for (int j = 0; carry || j < a.size(); j++) {",
		  "                carry += 1LL * v[i] * (j < a.size() ? a.v[j] : 0);",
		  "                while (i + j >= res.size())",
		  "                    res.v.push_back(0);",
		  "                carry += res.v[i + j];",
		  "                res.v[i + j] = carry % BASE;",
		  "                carry /= BASE;",
		  "            }",
		  "        }",
		  "        while (!res.v.empty() && res.v.back() == 0)",
		  "            res.v.pop_back();",
		  "        return res;",
		  "    }",
		  "",
		  "    BigInt& operator *= (const BigInt &a) {",
		  "        *this = *this * a;",
		  "        return *this;",
		  "    }",
		  "",
		  "    BigInt& operator -= (const BigInt &b){",
		  "        if(*this < b)",
		  "            throw(\"UNDERFLOW\");",
		  "        int n = this -> size(), m = b.size();",
		  "        int i, t = 0, s;",
		  "        for (i = 0; i < n;i++){",
		  "            if(i < m)",
		  "                s = this -> v[i] - b.v[i]+ t;",
		  "            else",
		  "                s = this -> v[i] + t;",
		  "            if(s < 0)",
		  "                s += 10,",
		  "                t = -1;",
		  "            else",
		  "                t = 0;",
		  "            this -> v[i] = s;",
		  "        }",
		  "        while(n > 1 && this -> v[n - 1] == 0)",
		  "            this -> v.pop_back(),",
		  "            n--;",
		  "        return *this;",
		  "    }",
		  "",
		  "    BigInt operator - (const BigInt&b){",
		  "        BigInt a = *this;",
		  "        a -= b;",
		  "        return a;",
		  "    }",
		  "",
		  "    BigInt operator -- (const int){",
		  "        *this -= BigInt(1);",
		  "        return *this;",
		  "    }",
		  "",
		  "    BigInt operator ++ (const int){",
		  "        *this += BigInt(1);",
		  "        return *this;",
		  "    }",
		  "",
		  "    BigInt& operator /=(const ll a) {",
		  "        ll carry = 0;",
		  "        for (int i = (int) v.size() - 1; i >= 0; i--) {",
		  "            ll cur = v[i] + carry * BASE;",
		  "            v[i] = cur / a;",
		  "            carry = cur % a;",
		  "        }",
		  "        while (!v.empty() && v.back() == 0)",
		  "            v.pop_back();",
		  "        return *this;",
		  "    }",
		  "    ",
		  "    BigInt operator / (const ll a) {",
		  "        ll carry = 0;",
		  "        vector < int > res = this -> v;",
		  "        for (int i = (int) res.size() - 1; i >= 0; i--) {",
		  "            ll cur = res[i] + carry * BASE;",
		  "            res[i] = cur / a;",
		  "            carry = cur % a;",
		  "        }",
		  "        BigInt ans;",
		  "        ans = res;",
		  "        return ans;",
		  "    }",
		  "    ",
		  "    BigInt operator % (const ll a){",
		  "        ll res = 0;",
		  "        for (int i = (int) v.size() - 1; i >= 0; i--)",
		  "            res = (res * 10 + v[i]) % a;",
		  "        BigInt ans = res;",
		  "        return ans;",
		  "    }",
		  "",
		  "    BigInt& operator %= (const ll a) {",
		  "        *this = *this % a;",
		  "        return *this;",
		  "    }",
		  "",
		  "    friend ostream& operator<<(ostream &out, const BigInt &a) {",
		  "        out << (a.zero() ? 0 : a.v.back());",
		  "        for (int i = (int) a.v.size() - 2; i >= 0; i--)",
		  "            out << setfill('0') << setw(9) << a.v[i];",
		  "        return out;",
		  "    }",
		  "",
		  "    friend istream& operator>>(istream &in, BigInt &a) {",
		  "        string s;",
		  "        in >> s;",
		  "        a = s;",
		  "        return in;",
		  "    }",
		  "",
		  "};"
		],
		"description": "Big Int Structure"
	},
    "Dijkstra": {
		"prefix": "Dijkstra",
		"body": [
		  "struct Dijkstra {",
		  "    ",
		  "    struct Edge {",
		  "",
		  "        ll v, w;",
		  "        ",
		  "        Edge(ll V = 0, ll W = 0): v(V), w(W) {}",
		  "        ",
		  "        bool operator < (const Edge& e) const {",
		  "            return w > e.w;",
		  "        }",
		  "    };",
		  "",
		  "    vector < vector < Edge > > adj;",
		  "",
		  "    Dijkstra(int edges, bool indirected = true){",
		  "        adj = vector < vector < Edge > > (edges);",
		  "        for(int i = 0, u, v, w; i < edges; i++){",
		  "            cin >> u >> v >> w;",
		  "            adj[u].push_back(Edge(v, w));",
		  "            if(indirected)",
		  "                adj[v].push_back(Edge(u, w));",
		  "        }",
		  "    }",
		  "",
		  "    ll Min_Cost(int src, int dest){",
		  "        int n = sz(adj);",
		  "        vector < ll > dist(n, LLONG_MAX);",
		  "        dist[src] = 0;",
		  "        priority_queue < Edge > Dij;",
		  "        Dij.push(Edge(src, 0));",
		  "        while(!Dij.empty()){",
		  "            auto [u, cost] = Dij.top();",
		  "            Dij.pop();",
		  "            for(auto& [v, w] : adj[u]){",
		  "                if(dist[v] > dist[u] + w){",
		  "                    dist[v] = dist[u] + w;",
		  "                    Dij.push(Edge(v, dist[v]));",
		  "                }",
		  "            }",
		  "        }",
		  "        return (dist[dest] == LLONG_MAX ? -1 : dist[dest]);",
		  "    }",
		  "",
		  "    vector < ll > get_dist(int src){",
		  "        int n = sz(adj);",
		  "        vector < ll > dist(n, LLONG_MAX);",
		  "        dist[src] = 0;",
		  "        priority_queue < Edge > Dij;",
		  "        Dij.push(Edge(src, 0));",
		  "        while(!Dij.empty()){",
		  "            auto [u, cost] = Dij.top();",
		  "            Dij.pop();",
		  "            for(auto& [v, w] : adj[u]){",
		  "                if(dist[v] > dist[u] + w){",
		  "                    dist[v] = dist[u] + w;",
		  "                    Dij.push(Edge(v, dist[v]));",
		  "                }",
		  "            }",
		  "        }",
		  "        return dist;",
		  "    }",
		  "",
		  "};"
		],
		"description": "Dijkstra"
	},
    "DSU": {
		"prefix": "DSU",
		"body": [
		  "template < typename T = int, int Base = 1 > struct DSU {",
		  "    ",
		  "    vector < T > parent, Gsize, nxt, tail, pos, roots;",
		  "",
		  "    DSU(int MaxNodes){",
		  "        parent = Gsize = roots = tail = pos = nxt = vector < T > (MaxNodes + Base);",
		  "        for(int i = Base; i < MaxNodes + Base; i++){",
		  "            parent[i] = roots[i] = pos[i] = tail[i] = i;",
		  "            nxt[i] = -1, Gsize[i] = 1;",
		  "        }",
		  "    }",
		  "    ",
		  "    T find_leader(int node){",
		  "        return parent[node] = (parent[node] == node ? node : find_leader(parent[node]));",
		  "    }",
		  "",
		  "    bool is_same_sets(int u, int v){",
		  "        return find_leader(u) == find_leader(v);",
		  "    }",
		  "",
		  "    void union_sets(int u, int v){",
		  "        int leader_u = find_leader(u), leader_v = find_leader(v);",
		  "        if(leader_u == leader_v) return;",
		  "        // make leader_u is the leader with the larger component",
		  "        if(Gsize[leader_u] < Gsize[leader_v]) ",
		  "            swap(leader_u, leader_v);",
		  "        int p = pos[leader_v];",
		  "        Gsize[leader_u] += Gsize[leader_v];",
		  "        parent[leader_v] = leader_u;",
		  "        roots[p] = roots.back();",
		  "        pos[roots[p]] = p;",
		  "        roots.pop_back();",
		  "        nxt[tail[leader_u]] = leader_v;",
		  "        tail[leader_u] = tail[leader_v];",
		  "    }",
		  "",
		  "    void print(){",
		  "        for(int root = Base; root < sz(roots); root++){",
		  "            for(int u = roots[root]; ~u ; u = nxt[u])",
		  "                cout << u << \" \\n\"[!~nxt[u]];",
		  "        }",
		  "    }",
		  "",
		  "    int get_size(int u){",
		  "        return Gsize[find_leader(u)];",
		  "    }",
		  "",
		  "    int get_components_number(){",
		  "        return sz(roots) - Base;",
		  "    }",
		  "};"
		],
		"description": "DSU"
	},
    "Sieve_Factorization": {
		"prefix": "Sieve_Factorization",
		"body": [
		  "struct Sieve_Factorization {",
		  "    ",
		  "    int n;",
		  "    vector < int > factors_cnt, prime_factors_cnt;",
		  "    vector < vector < int > > factors, prime_factors;",
		  "",
		  "    Factorization(int N){",
		  "        n = N;",
		  "        factors_cnt = vector < int > (n + 5, 2);",
		  "        prime_factors_cnt = vector < int > (n + 5);",
		  "        factors = vector < vector < int > > (n + 5);",
		  "        prime_factors = vector < vector < int > > (n + 5);",
		  "        factorization(n);",
		  "        prime_factorization(n);",
		  "    }",
		  "",
		  "    // Get the number of factors for each number",
		  "    void factorization(){ ",
		  "        factors_cnt[0] = 0, factors_cnt[1] = 1;",
		  "        for (int i = 2; i <= n; i++)  ",
		  "            for (int j = i + i; j <= n; j += i){",
		  "                factors_cnt[j]++;",
		  "                factors[j].push_back(i);",
		  "            }",
		  "    }",
		  "",
		  "    // get the number of factors of n",
		  "    int get_factors(int x){",
		  "        return factors_cnt[x];",
		  "    }",
		  "",
		  "    // get the factors of n",
		  "    vector < int > get_factors(){",
		  "        return factors[n];",
		  "    }",
		  "",
		  "    // Get the number of prime factors for each number",
		  "    void prime_factorization(){",
		  "        for (int i = 2; i <= n; i++){ ",
		  "            if (!prime_factors[i]) {",
		  "                for (int j = i; j <= n; j += i){ ",
		  "                    prime_factors[j]++;",
		  "                    prime_factors[j].push_back(i);",
		  "                }",
		  "            }",
		  "        }",
		  "    }",
		  "",
		  "    // get the number of prime factors of n",
		  "    int get_prime_factors(int x){",
		  "        return prime_factors[x];",
		  "    }",
		  "",
		  "    // get the prime factors of n",
		  "    vector < int > get_prime_factors(int x){",
		  "        return prime_factors[x];",
		  "    }",
		  "};"
		],
		"description": "Sieve_Factorization"
	},
    "Fenwick Tree": {
		"prefix": "Fenwick_Tree",
		"body": [
		  "template < typename T = int > struct Fenwick_Tree {",
		  "    ",
		  "    vector < T > Tree;",
		  "    int n;",
		  "    T DEFAULT;",
		  "",
		  "    Fenwick_Tree(int sz = 0){",
		  "        n = sz + 1, DEFAULT = 0;",
		  "        Tree = vector < T > (n + 10, DEFAULT);",
		  "    }",
		  "",
		  "    T operation(T a, T b){",
		  "        return a + b;",
		  "    }",
		  "",
		  "    int lowest_bit(int idx){",
		  "        return (idx & -idx);",
		  "    }",
		  "",
		  "    void build(vector < T >& nums){",
		  "        for(int i = 0; i < sz(nums); i++)",
		  "            add(i, nums[i]);",
		  "    }",
		  "",
		  "    void add(int idx, T val){",
		  "        idx++;",
		  "        while(idx <= n){",
		  "            Tree[idx] = operation(Tree[idx], val);",
		  "            idx += lowest_bit(idx);",
		  "        }",
		  "    }",
		  "",
		  "    T get_ans(int idx){",
		  "        T ans = DEFAULT;",
		  "        idx++;",
		  "        while(idx){",
		  "            ans = operation(ans, Tree[idx]);",
		  "            idx -= lowest_bit(idx);",
		  "        }",
		  "        return ans;",
		  "    }",
		  "",
		  "    T query(int l, int r){",
		  "        if(l > r) return DEFAULT;",
		  "        return get_ans(r) - get_ans(l - 1);",
		  "    }",
		  "",
		  "    T get(int idx){",
		  "        return query(idx, idx);",
		  "    }",
		  "",
		  "};"
		],
		"description": "Fenwick Tree"
	},
    "Fenwick_Tree_2D": {
		"prefix": "Fenwick_Tree_2D",
		"body": [
		  "template < typename T = int > struct Fenwick_Tree {",
		  "    ",
		  "    vector < vector < T > > Tree;",
		  "    int n, m;",
		  "    T DEFAULT;",
		  "",
		  "    Fenwick_Tree(int rows = 0, int cols = 0){",
		  "        n = rows + 1, m = cols + 1, DEFAULT = 0;",
		  "        Tree.assign(n + 10, vector < ll > (m + 10, DEFAULT));",
		  "    }",
		  "",
		  "    int lowest_bit(int idx){",
		  "        return (idx & -idx);",
		  "    }",
		  "",
		  "    void build(vector < vector < T > >& nums){",
		  "        for(int i = 0; i < sz(nums); i++)",
		  "            for(int j = 0; j < sz(nums[0]); j++)",
		  "                add(i + 1, j + 1, nums[i][j]);",
		  "    }",
		  "",
		  "    T operation(T a, T b){",
		  "        return a + b;",
		  "    }",
		  "",
		  "    void add(int idx, int jdx, T val){",
		  "        int i = idx + 1, j = jdx + 1;",
		  "        while(i <= n){",
		  "            j = jdx + 1;",
		  "            while(j <= m){",
		  "                Tree[i][j] = operation(Tree[i][j], val);",
		  "                j += lowest_bit(j);    ",
		  "            }",
		  "            i += lowest_bit(i);",
		  "        }",
		  "    }",
		  "",
		  "    T get_sum(int idx, int jdx){",
		  "        T sum = DEFAULT;",
		  "        int i = idx + 1, j = jdx + 1;",
		  "        while(i){",
		  "            j = jdx + 1;",
		  "            while(j){",
		  "                sum = operation(sum, Tree[i][j]);",
		  "                j -= lowest_bit(j);    ",
		  "            }",
		  "            i -= lowest_bit(i);",
		  "        }",
		  "        return sum;",
		  "    }",
		  "",
		  "    // Get the sum of the number in the rectangle x1, y1, x2, y2",
		  "",
		  "    T query(int x1, int y1, int x2, int y2) {",
		  "        if(x1 > x2) swap(x1, x2);",
		  "        if(y1 > y2) swap(y1, y2);",
		  "        return get_sum(x2, y2) - get_sum(x1 - 1, y2) - get_sum(x2, y1 - 1) + get_sum(x1 - 1, y1 - 1);",
		  "    }",
		  "",
		  "};"
		],
		"description": "Fenwick_Tree_2D"
	},
    "Floyd": {
		"prefix": "Floyd",
		"body": [
		  "template < typename T = int , int Base = 0 > struct Floyd {",
		  "    ",
		  "    int n;",
		  "    vector < vector < T > > dist;",
		  "    const T DEF = numeric_limits < T > :: max() / 2;",
		  "",
		  "    Floyd(int _n = 0) : n(_n), dist(n + 5, vector < T > (n + 5, DEF)) { ",
		  "        for(int i = 1; i <= n; i++)",
		  "            dist[i][i] = 0; // self loop",
		  "    }",
		  "",
		  "    Floyd(int _n, const vector < vector < T > > &D) : n(_n), dist(n + 5, vector < T > (n + 5, DEF)) { ",
		  "        for(int i = 1; i <= n; i++)",
		  "            for(int j = 1; j <= n; j++)",
		  "                dist[i][j] = D[i - !Base][j - !Base];",
		  "    }",
		  "",
		  "    T operation(T a, T b){",
		  "        return min(a, b);",
		  "    }",
		  "",
		  "    void add_edge(int u, int v, T w){",
		  "        dist[u][v] = operation(dist[u][v], w);",
		  "    }",
		  "",
		  "    void build(){",
		  "        for(int i = 1; i <= n; i++)",
		  "            for(int u = 1; u <= n; u++)",
		  "                for(int v = 1; v <= n; v++)",
		  "                    update_dist(u, v, i);",
		  "    }",
		  "",
		  "    T get_dist(int u, int v){",
		  "        return dist[u][v];",
		  "    }",
		  "",
		  "    void update_dist(int u, int v, int a, int b){",
		  "        dist[u][v] = operation(dist[u][v], dist[u][a] + dist[a][b] + dist[b][v]);",
		  "    }",
		  "",
		  "    void update_dist(int u, int v, int k){",
		  "        dist[u][v] = operation(dist[u][v], dist[u][k] + dist[k][v]);",
		  "    }",
		  "};",
		  ""
		],
		"description": "Floyd"
	},
    "Google": {
		"prefix": "Google",
		"body": [
		  "#include <bits/stdc++.h>",
		  "",
		  "using namespace std;",
		  "",
		  "#define cin_2d(vec, n, m) for(int i = 0; i < n; i++) for(int j = 0; j < m && cin >> vec[i][j]; j++);",
		  "#define cout_2d(vec, n, m) for(int i = 0; i < n; i++, cout << \"\\n\") for(int j = 0; j < m && cout << vec[i][j] << \" \"; j++);",
		  "#define fixed(n) fixed << setprecision(n)",
		  "#define ceil(n, m) (((n) / (m)) + ((n) % (m) ? 1 : 0))",
		  "#define fill(vec, value) memset(vec, value, sizeof(vec));",
		  "#define add_mod(a, b, m) (((a % m) + (b % m)) % m)",
		  "#define sub_mod(a, b, m) (((a % m) - (b % m) + m) % m)",
		  "#define mul_mod(a, b, m) (((a % m) * (b % m)) % m)",
		  "#define all(vec) vec.begin(), vec.end()",
		  "#define rall(vec) vec.rbegin(), vec.rend()",
		  "#define sz(x) int(x.size())",
		  "#define debug(x) cout << #x << \": \" << (x) << \"\\n\";",
		  "#define fi first",
		  "#define se second",
		  "#define ll long long",
		  "#define ull unsigned long long",
		  "#define Mod  1'000'000'007",
		  "#define OO 2'000'000'000",
		  "#define EPS 1e-9",
		  "#define PI acos(-1)",
		  "template < typename T = int > using Pair = pair < T, T >;",
		  "vector < string > RET = {\"NO\", \"YES\"};",
		  "",
		  "template < typename T = int > istream& operator >> (istream &in, vector < T > &v) {",
		  "    for (auto &x : v) in >> x;",
		  "    return in;",
		  "}",
		  "",
		  "template < typename T = int > ostream& operator << (ostream &out, const vector < T > &v) { ",
		  "    for (const T &x : v) out << x << ' '; ",
		  "    return out;",
		  "}",
		  "",
		  "void Solve(){",
		  "    ",
		  "}",
		  "",
		  "int main(){",
		  "    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);",
		  "    int t = 1;",
		  "    cin >> t;",
		  "    for(int tc = 1; tc <= t; tc++){",
		  "        cout << \"Case #\" << tc << \": \";",
		  "        Solve();",
		  "    }",
		  "    return 0;",
		  "}"
		],
		"description": "Google"
	},
    "Graph": {
		"prefix": "Graph",
		"body": [
		  "struct Graph {",
		  "",
		  "    int n, m, connected_components;",
		  "    vector < vector < int > > adj;",
		  "    vector < bool > vis;",
		  "    vector < int > depth, parent, deg, colour;",
		  "    ",
		  "    Graph(int N, int M){",
		  "        n = N, m = M;",
		  "        connected_components = 0;",
		  "        adj = vector < vector < int > > (n + 10);",
		  "        vis = vector < bool > (n + 10, false);",
		  "        depth = deg = colour = vector < int > (n + 10, 0);",
		  "        parent = vector < int > (n + 10, -1);",
		  "    }",
		  "",
		  "    void add_edge(int u, int v, bool is_directed = false){",
		  "        adj[u].push_back(v), deg[u]++; ",
		  "        if(!is_directed) ",
		  "            adj[v].push_back(u), deg[v]++;",
		  "    }",
		  "",
		  "    void remove_edge(int u, int v){",
		  "        adj[u].erase(find(all(adj[u]), v)), adj[v].erase(find(all(adj[v]), u));",
		  "    }",
		  "",
		  "    void build_adj(bool is_directed = false){",
		  "        for(int i = 0, u, v; i < m && cin >> u >> v; i++)",
		  "            add_edge(u, v, is_directed);",
		  "    }",
		  "",
		  "    void dfs(int node, int dep = 0, int par = -1){",
		  "        vis[node] = true, parent[node] = par, depth[node] = dep;",
		  "        for(auto& new_node : adj[node])",
		  "            if(!vis[new_node])",
		  "                dfs(new_node, dep + 1, node);",
		  "    }",
		  "",
		  "    bool is_cycle(int node, int par){",
		  "        vis[node] = true;",
		  "        for(auto& new_node : adj[node]){",
		  "            if(!vis[new_node]){",
		  "                if(is_cycle(new_node, node))",
		  "                    return true;",
		  "            }",
		  "            else if(new_node != par)",
		  "                return true;",
		  "        }",
		  "        return false;",
		  "    }",
		  "",
		  "    void get_path(int node){",
		  "        if(parent[node] == node) return;",
		  "        cout << node << \" \";",
		  "        get_path(parent[node]);",
		  "    }",
		  "",
		  "    void topology (){",
		  "        queue < int > topo;",
		  "        vector < int > graph;",
		  "        for(int i = 1; i <= n; i++)",
		  "            if(deg[i] == 1) topo.push(i), deg[i]--;",
		  "        while(!topo.empty()){",
		  "            int curr_node = topo.front();",
		  "            topo.pop();",
		  "            graph.push_back(curr_node);",
		  "            for(auto& new_node : adj[curr_node]){",
		  "                deg[new_node]--;",
		  "                if(deg[new_node] == 1)",
		  "                    topo.push(new_node);",
		  "            }",
		  "        }",
		  "        reverse(all(graph));",
		  "        cout << graph << \"\\n\";",
		  "    }",
		  "",
		  "    int bfs(int from, int to){",
		  "        if(from == to) return 0;",
		  "        queue < int > BFS;",
		  "        depth.assign(n + 10, OO);",
		  "        vis[from] = true, depth[from] = 0;",
		  "        BFS.push(from);",
		  "        while(!BFS.empty()){",
		  "            int sz = sz(BFS);",
		  "            while(sz--){",
		  "                int curr_node = BFS.front();",
		  "                BFS.pop();",
		  "                for(auto& new_node : adj[curr_node]){",
		  "                    if(!vis[new_node]){",
		  "                        BFS.push(new_node), parent[new_node] = curr_node; ",
		  "                        depth[new_node] = min(depth[new_node], depth[curr_node] + 1);",
		  "                        vis[new_node] = true;",
		  "                    }",
		  "                }",
		  "            }",
		  "        }",
		  "        return depth[to];",
		  "    }",
		  "",
		  "    bool is_Bipartite(int u){",
		  "        for(auto v : adj[u]){",
		  "            if(colour[v] == colour[u])",
		  "                return false;",
		  "            else if(colour[v] == 0){",
		  "                colour[v] = -colour[u];",
		  "                if(!is_Bipartite(v)){",
		  "                    return false;",
		  "                }",
		  "            }",
		  "        }",
		  "        return true;",
		  "    }",
		  "    ",
		  "    bool is_Bipartite(){",
		  "        for(int i = 1; i <= n; i++){",
		  "            if(colour[i] == 0) {",
		  "                colour[i] = -1;",
		  "                if(!is_Bipartite(i))",
		  "                    return false;",
		  "            }",
		  "        }",
		  "        return true;",
		  "    }",
		  "",
		  "};"
		],
		"description": "Graph"
	},
    "HLD": {
		"prefix": "HLD",
		"body": [
		  "template < typename T = int , int Base = 0 > struct Segment_Tree {",
		  "",
		  "    struct Node {",
		  "",
		  "        T val;",
		  "",
		  "        Node(T V = 0) : val(V) {}",
		  "    ",
		  "        Node operator = (const T rhs) {",
		  "            val = rhs;",
		  "            return *this;",
		  "        }",
		  "",
		  "    };",
		  "",
		  "    int size; ",
		  "    Node DEFAULT;",
		  "    vector < Node > tree; ",
		  "    #define LEFT (idx << 1)",
		  "    #define RIGHT ((idx << 1) | 1)",
		  "    #define VAL val",
		  "    ",
		  "    Segment_Tree(int n = 0){",
		  "        size = 1, DEFAULT = 0;",
		  "        while(size < n) size *= 2;",
		  "        tree = vector < Node > (2 * size, DEFAULT);",
		  "    }",
		  "",
		  "    Segment_Tree(int n, const vector < T >& nums){",
		  "        size = 1, DEFAULT = 0;",
		  "        while(size < n) size *= 2;",
		  "        tree = vector < Node > (2 * size, DEFAULT);",
		  "        build(nums);",
		  "    }",
		  "",
		  "    // Main operation to do",
		  "",
		  "    Node operation(const Node& a, const Node& b){",
		  "        return Node(max(a.VAL, b.VAL));",
		  "    }",
		  "    ",
		  "    // If Base is 1 so the array is 1-based else the array is 0-based",
		  "    ",
		  "    void build(const vector < T >& nums, int idx, int lx, int rx){",
		  "        if(Base ? lx >= sz(nums) : lx > sz(nums)) return;",
		  "        if(rx == lx) tree[idx] = nums[lx - !Base];",
		  "        else {",
		  "            int mx = (rx + lx) / 2;",
		  "            build(nums, LEFT, lx, mx);",
		  "            build(nums, RIGHT, mx + 1, rx);",
		  "            tree[idx] = operation(tree[LEFT], tree[RIGHT]);",
		  "        }",
		  "    }",
		  "",
		  "    void build(const vector < T >& nums){",
		  "        build(nums, 1, 1, size);",
		  "    }",
		  "",
		  "    void update(int index, T v, int idx, int lx, int rx){",
		  "        if(rx == lx) tree[idx] = v;",
		  "        else {  ",
		  "            int mx = (rx + lx) / 2;",
		  "            if(index <= mx) update(index, v, LEFT, lx, mx);",
		  "            else update(index, v, RIGHT, mx + 1, rx);",
		  "            tree[idx] = operation(tree[LEFT], tree[RIGHT]);",
		  "        }",
		  "    }",
		  "",
		  "    void update(const int index, const T v){",
		  "        update(index, v, 1, 1, size);",
		  "    }",
		  "",
		  "    Node query(int l, int r, int idx, int lx, int rx){",
		  "        if(lx > r || l > rx) return DEFAULT;",
		  "        if(lx >= l && rx <= r) return tree[idx];",
		  "        int mx = (lx + rx) / 2;",
		  "        return operation(query(l, r, LEFT, lx, mx), query(l, r, RIGHT, mx + 1, rx));",
		  "    }",
		  "",
		  "    Node query_Node(const int l, const int r){",
		  "        return query(l, r, 1, 1, size);",
		  "    }",
		  "",
		  "    T query(const int l, const int r){",
		  "        return query_Node(l, r).VAL;",
		  "    }",
		  "",
		  "    T get(const int idx){",
		  "        return query_Node(idx, idx).VAL;",
		  "    }",
		  "",
		  "    friend ostream& operator << (ostream &out, const Node &node) {",
		  "        out << node.VAL << ' ';",
		  "        return out;",
		  "    }",
		  "",
		  "    void print(int idx, int lx, int rx){",
		  "        if(lx == rx) cout << tree[idx] << ' ';",
		  "        else {",
		  "            int mx = (lx + rx) / 2;",
		  "            print(LEFT, lx, mx);",
		  "            print(RIGHT, mx + 1, rx);",
		  "        }",
		  "    }",
		  "",
		  "    void print(){",
		  "        print(1, 1, size);",
		  "        cout << '\\n';",
		  "    }",
		  "    ",
		  "    // remove macro LEFT and RIGHT",
		  "    #undef LEFT",
		  "    #undef RIGHT",
		  "    #undef VAL",
		  "};",
		  "",
		  "template < typename T = int, const int VAL_ON_EDGE = 0 > struct HLD {",
		  "    // VAL_ON_EDGE = 0 if value on nodes",
		  "    // VAL_ON_EDGE = 1 if value on edges",
		  "",
		  "    const vector < vector < Pair < T > > > &adj;",
		  "    vector < T > dep, par, root, pos, SubtreeSz, child;",
		  "    int nxtPos;",
		  "    Segment_Tree < T > seg;",
		  "",
		  "    #define loop(v, w, ADJ) for(auto [v, w] : ADJ)",
		  "",
		  "    HLD(int n, const vector < vector < Pair < T > > >& G, int treeRoot = 1) : adj(G) {",
		  "        nxtPos = 1;",
		  "        // child is heavy child",
		  "        dep = par = root = pos = SubtreeSz = child = vector < T > (n + 5);",
		  "        init(treeRoot);",
		  "        build(treeRoot);",
		  "        seg = Segment_Tree < T > (n + 5);",
		  "    }",
		  "",
		  "    // init the tree",
		  "    void init(int u, int p = -1, int d = 0){",
		  "        dep[u] = d, par[u] = p, SubtreeSz[u] = 1;",
		  "        loop(v, w, adj[u]){",
		  "            if (v == p) continue;",
		  "            init(v, u, d + 1);",
		  "            SubtreeSz[u] += SubtreeSz[v];",
		  "            if (SubtreeSz[v] > SubtreeSz[child[u]]) ",
		  "                child[u] = v;",
		  "        }",
		  "    } ",
		  "",
		  "    // get the root of the chain",
		  "    int get_lca(int u, int v){",
		  "        while (root[u] != root[v]){",
		  "            if (dep[root[u]] < dep[root[v]]) ",
		  "                swap(u, v);",
		  "            u = par[root[u]];",
		  "        }",
		  "        return dep[u] < dep[v] ? u : v;",
		  "    }",
		  "",
		  "    // build the chains",
		  "    void build(int u, bool newChain = true){",
		  "        root[u] = newChain ? u : root[par[u]];",
		  "        pos[u] = nxtPos++;",
		  "        if (child[u]) ",
		  "            build(child[u], false);",
		  "        loop(v, w, adj[u]){",
		  "            if(v == par[u] || v == child[u]) continue;",
		  "            build(v, true);",
		  "        }",
		  "    }",
		  "",
		  "    // make u lower",
		  "    void makeULower(int& u, int& v){",
		  "        if(dep[root[u]] < dep[root[v]] || (root[u] == root[v] && dep[u] < dep[v]))",
		  "            swap(u, v);",
		  "    }",
		  "",
		  "    // move up the chain and also change the next position",
		  "    Pair < T > moveUp(int& u){",
		  "        Pair < T > ret = {pos[root[u]], pos[u]};",
		  "        u = par[root[u]];",
		  "        return ret;",
		  "    }",
		  "",
		  "    vector < Pair < T > > queryPath(int u, int v){",
		  "        // return all ranges in segment tree",
		  "        vector < Pair < T > > ret;",
		  "        while(root[u] != root[v]){",
		  "            makeULower(u, v);",
		  "            ret.push_back(moveUp(u));",
		  "        }",
		  "        // add range between u and v",
		  "        makeULower(u, v);",
		  "        if(!VAL_ON_EDGE) // value on nodes",
		  "            ret.push_back({pos[v], pos[u]});",
		  "        else if(u != v) // don't include the root node",
		  "            ret.push_back({pos[v] + 1, pos[u]});",
		  "        return ret;",
		  "    }",
		  "",
		  "    // get child of a node for problem that value on edges",
		  "    int getChild(int u, int v){",
		  "        if(par[u] == v) ",
		  "            return u;",
		  "        return v;",
		  "    }",
		  "",
		  "    // update value of node u",
		  "    void update(int u, T val){",
		  "        seg.update(pos[u], val);",
		  "    }",
		  "",
		  "    // update value of edge u-v",
		  "    void update(int u, int v, T val){",
		  "        u = getChild(u, v);",
		  "        seg.update(pos[u], val);",
		  "    }",
		  "",
		  "    // query value",
		  "    T query(int u_q, int v_q){",
		  "        T ret = 0;",
		  "        for(auto& [u, v] : queryPath(u_q, v_q))",
		  "            ret = max(ret, seg.query(u, v));",
		  "        return ret;",
		  "    }",
		  "",
		  "    #undef loop",
		  "};"
		],
		"description": "HLD"
	},
    "Kadane": {
		"prefix": "Kadane",
		"body": [
		  "template < typename T = int > struct Kadane {",
		  "    ",
		  "    // Minimum Contigours Subarray Sum",
		  "",
		  "    Kadane(){};",
		  "",
		  "    T Min_Subarray_Sum(vector < T >& nums){",
		  "        T Min_so_far = OO, Min_Curr = 0, DEFAULT = 0;",
		  "        for(auto& i : nums){",
		  "            Min_Curr += i;",
		  "            Min_so_far = min(Min_so_far, Min_Curr);",
		  "            Min_Curr = min(Min_Curr, DEFAULT);",
		  "        }",
		  "        return Min_so_far;",
		  "    }",
		  "",
		  "    // Maximum Contigours Subarray Sum",
		  "",
		  "    T Max_Subarray_Sum(vector < T >& nums){",
		  "        T Max_so_far = -OO, Max_Curr = 0, DEFAULT = 0;",
		  "        for(auto& i : nums){",
		  "            Max_Curr += i;",
		  "            Max_so_far = max(Max_so_far, Max_Curr);",
		  "            Max_Curr = max(Max_Curr, DEFAULT);",
		  "        }",
		  "        return Max_so_far;",
		  "    }",
		  "",
		  "};",
		  ""
		],
		"description": "Kadane"
	},
    "Lazy_Propagation": {
		"prefix": "Lazy_Propagation",
		"body": [
			"template < typename T = int , const int Base = 0 >",
			"class Lazy_Propagation {",
			"private:",
			"    struct Node {",
			"        T val, update;",
			"        bool is_lazy;",
			"        Node(T V = 0) : val(V), update(0), is_lazy(false) {}",
			"    };",
			"",
			"    int size, max_level;",
			"    T query_default, init_default;",
			"    vector < Node > tree;",
			"",
			"    // Lazy operation function",
			"    T lazy_operation(T a, T b) {",
			"        return a + b; // Change this to your specific lazy operation",
			"    }",
			"",
			"    // Tree operation function",
			"    Node tree_operation(const Node& a, const Node& b) {",
			"        return Node(a.val + b.val); // Change this to your specific tree operation",
			"    }",
			"",
			"    // Push lazy value to children",
			"    void propagate(int idx, int lx, int rx) {",
			"        if (!tree[idx].is_lazy) return;",
			"        tree[idx].val = lazy_operation(tree[idx].val, (rx - lx + 1) * tree[idx].update);",
			"        if (lx != rx) {",
			"            tree[idx * 2].update = lazy_operation(tree[idx * 2].update, tree[idx].update);",
			"            tree[idx * 2 + 1].update = lazy_operation(tree[idx * 2 + 1].update, tree[idx].update);",
			"            tree[idx * 2].is_lazy = tree[idx * 2 + 1].is_lazy = true;",
			"        }",
			"        tree[idx].update = init_default;",
			"        tree[idx].is_lazy = false;",
			"    }",
			"",
			"    // Update lazy value",
			"    void update_lazy(int idx, T v) {",
			"        tree[idx].update = lazy_operation(tree[idx].update, v);",
			"        tree[idx].is_lazy = true;",
			"    }",
			"",
			"    // Build tree with initial value or vector of values",
			"    void build(const vector<T>& nums, const T initial_value, int idx, int lx, int rx) {",
			"        if (!nums.empty() && (Base ? lx >= int(nums.size()) : lx > int(nums.size()))) return;",
			"        if (rx == lx) tree[idx] = !nums.empty() ? Node(nums[lx - !Base]) : Node(initial_value);",
			"        else {",
			"            int mx = (lx + rx) / 2;",
			"            build(nums, initial_value, idx * 2, lx, mx);",
			"            build(nums, initial_value, idx * 2 + 1, mx + 1, rx);",
			"            propagate(idx * 2, lx, mx);",
			"            propagate(idx * 2 + 1, mx + 1, rx);",
			"            tree[idx] = tree_operation(tree[idx * 2], tree[idx * 2 + 1]);",
			"        }",
			"    }",
			"",
			"    void update(int l, int r, T v, int idx, int lx, int rx) {",
			"        propagate(idx, lx, rx);",
			"        if (lx >= l && rx <= r) return update_lazy(idx, v);",
			"        if (lx > r || rx < l) return;",
			"        int mx = (lx + rx) / 2;",
			"        update(l, r, v, idx * 2, lx, mx);",
			"        update(l, r, v, idx * 2 + 1, mx + 1, rx);",
			"        propagate(idx * 2, lx, mx);",
			"        propagate(idx * 2 + 1, mx + 1, rx);",
			"        tree[idx] = tree_operation(tree[idx * 2], tree[idx * 2 + 1]);",
			"    }",
			"",
			"    T query(int l, int r, int idx, int lx, int rx) {",
			"        propagate(idx, lx, rx);",
			"        if (lx >= l && rx <= r) return tree[idx].val;",
			"        if (lx > r || rx < l) return query_default;",
			"        int mx = (lx + rx) / 2;",
			"        T left_result = query(l, r, idx * 2, lx, mx);",
			"        T right_result = query(l, r, idx * 2 + 1, mx + 1, rx);",
			"        return lazy_operation(left_result, right_result);",
			"    }",
			"",
			"public:",
			"",
			"    Lazy_Propagation(int n, const vector < T >& v = vector < T > ()) : size(1), max_level(1), query_default(0), init_default(0)  {",
			"        while (size <= n) size *= 2, max_level++;",
			"        tree = vector < Node > (2 * size, Node(init_default));",
			"        if (!v.empty()) build(v);",
			"    }",
			"",
			"    void build(const T initial_value) {",
			"        build(vector < T >(), initial_value, 1, 1, size);",
			"    }",
			"",
			"    void build(const vector < T >& nums) {",
			"        build(nums, init_default, 1, 1, size);",
			"    }",
			"",
			"    void update(int i, T v) {",
			"        update(i, i, v, 1, 1, size);",
			"    }",
			"",
			"    void update(int l, int r, T v) {",
			"        update(l, r, v, 1, 1, size);",
			"    }",
			"",
			"    T query(int l, int r) {",
			"        return query(l, r, 1, 1, size);",
			"    }",
			"",
			"    T get(int i) {",
			"        return query(i, i, 1, 1, size);",
			"    }",
			"",
			"    void print() {",
			"        if (tree.size() <= 1) return;",
			"        int level = 0;",
			"        queue < tuple<int, int, int, int> > q;  // pair of (index in tree, level in tree, lx, rx)",
			"        q.push({1, level, 1, size});",
			"        while (!q.empty()) {",
			"            int nodesAtCurrentLevel = q.size();",
			"            int spacesBetween = (1 << (max_level - level + 1)) - 1;",
			"            int leadingSpaces = (1 << (max_level - level)) - 1;",
			"            cout << string(leadingSpaces * 2, ' ');",
			"            while (nodesAtCurrentLevel--) {",
			"                auto [idx, lvl, lx, rx] = q.front();",
			"                q.pop();            ",
			"                // Propagate lazy values",
			"                propagate(idx, lx, rx);",
			"                cout << setw(2) << tree[idx].val;",
			"                // Print spaces between nodes at the current level",
			"                if (nodesAtCurrentLevel) cout << string(spacesBetween * 2, ' ');",
			"                // Add children to the queue",
			"                if (idx * 2 < tree.size()) {",
			"                    int mx = (lx + rx) / 2;",
			"                    q.push({idx * 2, lvl + 1, lx, mx});",
			"                    q.push({idx * 2 + 1, lvl + 1, mx + 1, rx});",
			"                }",
			"            }",
			"            cout << \"\\n\";  // new line for the new level",
			"            level++;",
			"        }",
			"    }",
			"};"
		],
		"description": "Lazy_Propagation"
	},
    "LCA": {
		"prefix": "LCA",
		"body": [
			"template < typename vecType = int >",
			"class LCA {",
			"public:",
			"    LCA(",
			"        int n = 0,",
			"        const vector < vector < int > > &G = {},",
			"        int root = 1",
			"    ) : N(n), LOG(0), ROOT(root), adj(G) {",
			"        while((1 << LOG) <= N) LOG++;",
			"        anc.assign(N + 5, vector < int > (LOG));",
			"        depth.assign(N + 5, 0);",
			"        dfs(ROOT);",
			"    }",
			"",
			"    int kth_ancestor(int u, int k) const {",
			"        if(depth[u] < k) return -1;",
			"        for(int bit = 0; bit < LOG; bit++)",
			"            if(k & (1 << bit)) ",
			"                u = anc[u][bit];",
			"        return u;",
			"    }",
			"",
			"    int get_lca(int u, int v) const {",
			"        if(depth[u] < depth[v]) swap(u, v);",
			"",
			"        u = kth_ancestor(u, depth[u] - depth[v]);",
			"        if(u == v) return u;",
			"        ",
			"        for(int bit = LOG - 1; bit >= 0; bit--)",
			"            if(anc[u][bit] != anc[v][bit])",
			"                u = anc[u][bit], v = anc[v][bit];",
			"        ",
			"        return anc[u][0];",
			"    }",
			"",
			"    int get_dist(int u, int v) const {",
			"        return depth[u] + depth[v] - 2 * depth[get_lca(u, v)];",
			"    }",
			"",
			"private:",
			"    int N, LOG, ROOT;",
			"    const vector < vector < int > > &adj;",
			"    vector < vector < int > > anc;",
			"    vector < int > depth;",
			"",
			"    void dfs(int u, int p = 0){",
			"        for(int v : adj[u]){",
			"            if(v == p) continue;",
			"            depth[v] = depth[u] + 1;",
			"            anc[v][0] = u;",
			"            for(int bit = 1; bit < LOG; bit++){",
			"                anc[v][bit] = anc[anc[v][bit - 1]][bit - 1];",
			"            }",
			"            dfs(v, u);",
			"        }",
			"    }",
			"};",
			""
		],
		"description": "LCA"
	},
	"LCA Weighted": {
		"prefix": "LCA Weighted",
		"body": [
			"template < typename treeType = int >",
			"class LCA {",
			"public:",
			"    LCA(",
			"        int n = 0,",
			"        const vector < vector < pair < int, treeType > > > &G = {},",
			"        function < treeType(treeType, treeType) > op = [](treeType a, treeType b){ return a + b; },",
			"        treeType _neutral = treeType(),",
			"        int root = 1",
			"    ) : N(n), LOG(0), ROOT(root), adj(G), operation(op), neutral(_neutral) {",
			"        while((1 << LOG) <= N) LOG++;",
			"        anc.assign(N + 5, vector < int > (LOG));",
			"        cost.assign(N + 5, vector < treeType > (LOG, neutral));",
			"        depth.assign(N + 5, 0);",
			"        dfs(ROOT);",
			"    }",
			"",
			"    int kth_ancestor(int u, int k) const {",
			"        if(depth[u] < k) return -1;",
			"        for(int bit = 0; bit < LOG; bit++)",
			"            if(k & (1 << bit)) ",
			"                u = anc[u][bit];",
			"        return u;",
			"    }",
			"",
			"    int get_lca(int u, int v) const {",
			"        if(depth[u] < depth[v]) swap(u, v);",
			"",
			"        u = kth_ancestor(u, depth[u] - depth[v]);",
			"        if(u == v) return u;",
			"        ",
			"        for(int bit = LOG - 1; bit >= 0; bit--)",
			"            if(anc[u][bit] != anc[v][bit])",
			"                u = anc[u][bit], v = anc[v][bit];",
			"        ",
			"        return anc[u][0];",
			"    }",
			"",
			"    treeType query(int u, int v) const {",
			"        int lca = get_lca(u, v);",
			"        return operation(get_cost(u, depth[u] - depth[lca]), get_cost(v, depth[v] - depth[lca]));",
			"    }",
			"",
			"private:",
			"    int N, LOG, ROOT;",
			"    const vector < vector < pair < int, treeType > > > &adj;",
			"    vector < vector < int > > anc;",
			"    vector < vector < treeType > > cost;",
			"    vector < int > depth;",
			"    function < treeType(treeType, treeType) > operation;",
			"    treeType neutral;",
			"",
			"    void dfs(int u, int p = 0){",
			"        for(auto& [v, w] : adj[u]){",
			"            if(v == p) continue;",
			"            depth[v] = depth[u] + 1;",
			"            anc[v][0] = u, cost[v][0] = w;",
			"            for(int bit = 1; bit < LOG; bit++){",
			"                anc[v][bit] = anc[anc[v][bit - 1]][bit - 1];",
			"                cost[v][bit] = operation(cost[v][bit - 1], cost[anc[v][bit - 1]][bit - 1]);",
			"            }",
			"            dfs(v, u);",
			"        }",
			"    }",
			"",
			"    treeType get_cost(int u, int dist) const {",
			"        if(depth[u] < dist) return neutral;",
			"        treeType ret = neutral;",
			"        for(int bit = 0; bit < LOG; bit++){",
			"            if(dist & (1 << bit)){",
			"                ret = operation(ret, cost[u][bit]);",
			"                u = anc[u][bit];",
			"            }",
			"        }",
			"        return ret;",
			"    }",
			"};"
		],
		"description": "LCA Weighted"
	},
    "Mancher": {
		"prefix": "Mancher",
		"body": [
		  "string longestPalSubstring(string& s){",
		  "    int strLen = 2 * sz(s) + 3, maxLen = 0, start = 0, maxRight = 0 ,center = 0;",
		  "    string str = \"@#\";",
		  "    for (char& c : s)",
		  "        str.push_back(c), str.push_back('#');",
		  "    str.push_back('$');",
		  "    vector < int > p(strLen);",
		  "    for(int i = 1; i < strLen - 1; i++){",
		  "        if (i < maxRight)",
		  "            p[i] = min(maxRight - i, p[2 * center - i]);",
		  "        while (str[i + p[i] + 1] == str[i - p[i] - 1]) p[i]++;",
		  "        if (i + p[i] > maxRight)",
		  "            center = i, maxRight = i + p[i];",
		  "        if (p[i] > maxLen)",
		  "            start = (i - p[i] - 1) / 2, maxLen = p[i];",
		  "    }",
		  "    return s.substr(start, maxLen);",
		  "}"
		],
		"description": "Mancher"
	},
    "Math": {
		"prefix": "Math",
		"body": [
		  "struct Math {",
		  "",
		  "    Math(){}",
		  "",
		  "    // Greatest common divisors between two numbers",
		  "",
		  "    ll GCD(ll a, ll b){",
		  "        return (!b ? a : GCD(b, a % b));",
		  "    }",
		  "    ",
		  "    // least common multiplication between two numbers",
		  "",
		  "    ll LCM(ll a, ll b){",
		  "        return a / GCD(a, b) * b;",
		  "    }",
		  "",
		  "    // Get vector with the prime factors of number",
		  "",
		  "    vector < int > prime_factorization(ll n){",
		  "        vector < int > factors;",
		  "        while(n % 2 == 0) factors.push_back(2), n /= 2;",
		  "        for(int i = 3; i <= sqrt(n); i += 2)",
		  "            while(n % i == 0) factors.push_back(i), n /= i;",
		  "        if(n > 2) factors.push_back(n);",
		  "        return factors;",
		  "    }",
		  "",
		  "    // Combination",
		  "",
		  "    ll nCr(ll n, ll r){",
		  "        if(r > n) return 0;",
		  "        ll p = 1, k = 1;",
		  "        if (n - r < r) r = n - r;",
		  "        // condition for minimum choose",
		  "        if(n < 1) return 0;",
		  "        while (r > 0){",
		  "            p *= n, k *= r;",
		  "            ll m = __gcd(p, k);",
		  "            p /= m, k /= m, n--, r--;        ",
		  "        }",
		  "        return p;",
		  "    }",
		  "",
		  "    // Permutation",
		  "",
		  "    ll nPr(ll n, ll r){",
		  "        if(r > n) return 0;",
		  "        ll npr = 1;",
		  "        while(r-- > 0)",
		  "            npr *= n--;",
		  "        return npr;",
		  "    }",
		  "",
		  "    // get a mod for big int",
		  "",
		  "    ll Big_Mod(string s, ll mod){",
		  "        ll res = 0;",
		  "        for(auto& c : s)",
		  "            res = (res * 10 + (c - '0')) % mod;",
		  "        return res;",
		  "    }",
		  "",
		  "    // add two number and take mod for them",
		  "",
		  "    void add(ll& a, ll b, ll mod = 1e9 + 7){",
		  "        a += b;",
		  "        if(a >= mod)",
		  "            a -= mod;",
		  "    }",
		  "",
		  "    // multiply two number and take mod for them",
		  "",
		  "    void mul(ll& a, ll b, ll mod = 1e9 + 7){",
		  "        a = ((a % mod) * (b % mod)) % mod;",
		  "    }",
		  "",
		  "    // b power e in O(log(n))",
		  "",
		  "    ll Bin_Pow(ll b, ll e){",
		  "        ll power = 1;",
		  "        while(e){",
		  "            if(e & 1) power *= b;",
		  "            e >>= 1;",
		  "            b *= b;",
		  "        }",
		  "        return power;",
		  "    }",
		  "",
		  "    // b power e % mod in O(log(e))",
		  "",
		  "    ll Bin_Pow(ll b, ll e, ll mod){",
		  "        ll power = 1;",
		  "        while(e){",
		  "            if(e & 1) mul(power, b, mod);",
		  "            e >>= 1;",
		  "            mul(b, b, mod);",
		  "        }",
		  "        return power % mod;",
		  "    }",
		  "",
		  "    // b multiply e % mod in O(log(e))",
		  "",
		  "    ll Bin_Mul(ll b, ll e, ll mod){",
		  "        ll mult = 0;",
		  "        while(e){",
		  "            if(e & 1) add(mult, b, mod);",
		  "            e >>= 1;",
		  "            add(b, b, mod);",
		  "        }",
		  "        return mult % mod;",
		  "    }",
		  "",
		  "    // Check if number is prime or not",
		  "",
		  "    bool is_prime(ll n){",
		  "        if(n < 2 || (n % 2 == 0 && n != 2)) return false;",
		  "        for(int i = 3; i <= sqrt(n); i += 2)",
		  "            if(n % i == 0) return false;",
		  "        return true;",
		  "    }",
		  "",
		  "    // get the number of divisors for n",
		  "",
		  "    int number_of_divisors(ll n){",
		  "        int divisors = 0;",
		  "        for(int i = 1; i < sqrt(n); i++)",
		  "            if(n % i == 0) divisors += 2;",
		  "        return divisors + (sqrt(n) == (int)sqrt(n));",
		  "    }",
		  "",
		  "    // get Summation of divisors for n",
		  "",
		  "    ll sum_of_divisors(ll n){",
		  "        ll sum_divisors = 0;",
		  "        for(int i = 1; i < sqrt(n); i++)",
		  "            if(n % i == 0) sum_divisors += ((n / i) + i);",
		  "        ll sq = sqrt(n);",
		  "        return sum_divisors + (sq * sq == n ? sq : 0);",
		  "    }",
		  "",
		  "    // get vector with the divisors for n",
		  "",
		  "    vector < ll > Get_Divisors(ll n){",
		  "        vector < ll > divisors;",
		  "        for(int i = 1; i < sqrt(n); i++)",
		  "            if(n % i == 0) divisors.push_back(i), divisors.push_back(n / i);",
		  "        if(sqrt(n) == int(sqrt(n))) divisors.push_back(sqrt(n));",
		  "        return divisors;",
		  "    }",
		  "",
		  "    // print all permutation of an array",
		  "",
		  "    void Print_Permutation(vector < int >& nums){",
		  "        sort(all(nums));",
		  "        do {",
		  "            for(auto& i : nums)",
		  "                cout << i << \" \";",
		  "            cout << \"\\n\";",
		  "        } while(next_permutation(nums.begin(), nums.end()));",
		  "    }",
		  "",
		  "    // print all permutation of a string",
		  "",
		  "    void Print_Permutation(string s){",
		  "        sort(all(s));",
		  "        do {",
		  "            cout << s << \"\\n\";",
		  "        } while(next_permutation(s.begin(), s.end()));",
		  "    }",
		  "",
		  "    // get the summation between two numbers or the summation between 1 and n",
		  "",
		  "    ll Summation(ll r, ll l = 0){",
		  "        if(l > r) swap(l, r);",
		  "        return (r * (r + 1) / 2) - (l * (l - 1) / 2);",
		  "    }",
		  "",
		  "    // Get how many number divisable by c between a and b",
		  "",
		  "    ll how_many_divisors(ll a, ll b, ll c){",
		  "        return (b / c) - ((a - 1) / c);",
		  "    }",
		  "",
		  "    // Get summation of numbers divisable by c between a and b",
		  "",
		  "    ll Summation_of_Devisors(ll a, ll b, ll c){",
		  "        ll right = Summation(b / c);",
		  "        ll left = Summation((a - 1) / c);",
		  "        return (right - left) * c;",
		  "    }",
		  "",
		  "    // get logb(a)",
		  "",
		  "    double get_log(ll a, int b){",
		  "        return log(a) / log(b);",
		  "    }",
		  "",
		  "    // Check if number power of another or not",
		  "",
		  "    bool is_power(ll number, int base = 2){",
		  "        return (get_log(number, base) - (ll) get_log(number, base) <= EPS);",
		  "    }",
		  "",
		  "    // Distination Between two points",
		  "",
		  "    double dist(double x1, double y1, double x2, double y2){",
		  "        return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));",
		  "    }",
		  "",
		  "    // Check if it valid triangle with 3 length sides",
		  "",
		  "    bool is_triangle(ll a, ll b, ll c){",
		  "        return (a + b > c) && (a + c > b) && (b + c > a) && (a && b && c);",
		  "    }",
		  "",
		  "    // Get Slope of two points",
		  "",
		  "    double slope(double x1, double y1, double x2, double y2){",
		  "        if(x2 == x1) return 0;",
		  "        return (y2 - y1) / (x2 - x1);",
		  "    }",
		  "",
		  "    // Check if three points in the same line",
		  "",
		  "    bool is_same_line(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){",
		  "        return (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1);",
		  "    }",
		  "",
		  "    // Check if is perfect square",
		  "",
		  "    bool is_perfect_square(ll n){",
		  "        ll sq = sqrt(n);",
		  "        return sq * sq == n;",
		  "    }",
		  "",
		  "    // Convert Decimal to any base",
		  "",
		  "    string decimal_to_any_base(ll decimal, ll base){",
		  "        if(decimal == 0) return \"0\";",
		  "        string num = \"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\";",
		  "        string result;",
		  "        do{",
		  "            result.push_back(num[decimal % base]);",
		  "            decimal /= base;",
		  "        }while(decimal != 0);",
		  "        return string(result.rbegin(), result.rend());",
		  "    }",
		  "    ",
		  "    // Convert any base to decimal",
		  "",
		  "    ll  any_base_to_decimal(string str, int base) {",
		  "        auto val = [](char c){",
		  "            return (c >= '0' && c <= '9' ? (int) c - '0' : (int) c - 'A' + 10);",
		  "        };",
		  "        ll len = sz(str), power = 1, num = 0, i;",
		  "        for (i = len - 1; i >= 0; i--) {",
		  "            num += val(str[i]) * power;",
		  "            power = power * base;",
		  "        }",
		  "        return num;",
		  "    }",
		  "",
		  "};"
		],
		"description": "Math"
	},
    "MoAlgorithm": {
		"prefix": "MoAlgorithm",
		"body": [
			"template < typename T = int, int Base = 0 >",
			"class MoAlgorithm {",
			"public:",
			"    struct query {",
			"        int l, r, query_idx;",
			"        int64_t ord;",
			"",
			"        query(int L = 0, int R = 0, int Query_idx = 0, int HilbertPow = 0) {",
			"            l = L - !Base, r = R - !Base, query_idx = Query_idx;",
			"            calcOrder(HilbertPow);",
			"        }",
			"",
			"        void calcOrder(int HilbertPow) {",
			"            ord = gilbertOrder(l, r, HilbertPow, 0);",
			"        }",
			"",
			"        bool operator < (const query& rhs) const {",
			"            return ord < rhs.ord;",
			"        }",
			"    };",
			"",
			"    MoAlgorithm(int N = 0, int M = 0) : currL(1), currR(0), n(N), m(M), sqrtN(n / sqrt(m) + 1), hilbertPow(calculateHilbertPow()), ans(0), answers(m), queries(m) {}",
			"",
			"    void getData(const vector < T >& v = {}){",
			"        val = v;",
			"        ",
			"        for (int i = 0, l, r; i < m && cin >> l >> r; i++)",
			"            queries[i] = query(l, r, i, hilbertPow);",
			"        ",
			"        process();",
			"    }",
			"",
			"    void process() {",
			"        sort(queries.begin(), queries.end());",
			"        currL = queries[0].l, currR = queries[0].l - 1;",
			"",
			"        for (auto& q : queries) {",
			"            setRange(q);",
			"            answers[q.query_idx] = ans;",
			"        }",
			"    }",
			"",
			"    vector < T > getAnswers() const {",
			"        return answers;",
			"    }",
			"",
			"private:",
			"    int currL, currR, n, m, sqrtN, hilbertPow;",
			"    T ans;",
			"    vector < T > answers, val;",
			"    vector < query > queries;",
			"",
			"    static int64_t gilbertOrder(int x, int y, int pow, int rotate) {",
			"        if (pow == 0) return 0;",
			"        int hpow = 1 << (pow - 1);",
			"        int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);",
			"        seg = (seg + rotate) & 3;",
			"        const int rotateDelta[4] = {3, 0, 0, 1};",
			"        int nx = x & (x ^ hpow), ny = y & (y ^ hpow);",
			"        int nrot = (rotate + rotateDelta[seg]) & 3;",
			"        int64_t subSquareSize = int64_t(1) << (2 * pow - 2);",
			"        int64_t ordd = seg * subSquareSize;",
			"        int64_t add = gilbertOrder(nx, ny, pow - 1, nrot);",
			"        ordd += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);",
			"        return ordd;",
			"    }",
			"",
			"    int calculateHilbertPow() const {",
			"        int pow = 1;",
			"        while ((1 << pow) < n) pow++;",
			"        return pow;",
			"    }",
			"",
			"    void add(int idx) {",
			"        // add idx to the processing range",
			"    }",
			"",
			"    void remove(int idx) {",
			"        // remove idx from the processing range",
			"    }",
			"",
			"    void setRange(const query& q) {",
			"        while (currL > q.l) currL--, add(currL);",
			"        while (currR < q.r) currR++, add(currR);",
			"        while (currL < q.l) remove(currL), currL++;",
			"        while (currR > q.r) remove(currR), currR--;",
			"    }",
			"};",
			""
		],
		"description": "MoAlgorithm"
	},
    "ModInt": {
		"prefix": "ModInt",
		"body": [
		  "template < int MOD = 1000000007, typename T = int > struct ModInt {",
		  "",
		  "    T val;",
		  "",
		  "    ModInt(T V = 0) : val(V) { val %= MOD; }",
		  "",
		  "    ModInt& operator += (const ModInt& rhs) {",
		  "        if ((val += rhs.val) >= MOD) val -= MOD;",
		  "        return *this;",
		  "    }",
		  "    ModInt& operator += (const T rhs) {",
		  "        if ((val += rhs) >= MOD) val -= MOD;",
		  "        return *this;",
		  "    }",
		  "",
		  "    ModInt& operator -= (const ModInt& rhs) { ",
		  "        if ((val += MOD - rhs.val) >= MOD) val -= MOD; ",
		  "        return *this; ",
		  "    }",
		  "    ModInt& operator -= (const T rhs) { ",
		  "        if ((val += MOD - rhs) >= MOD) val -= MOD; ",
		  "        return *this; ",
		  "    }",
		  "",
		  "    ModInt& operator *= (const ModInt& rhs) { val = (1ll * val * rhs.val) % MOD; return *this; }",
		  "    ModInt& operator *= (const T rhs) { val = (1ll * val * rhs) % MOD; return *this; }",
		  "",
		  "    ModInt& operator /= (const ModInt& rhs) { return *this *= rhs.inverse(); }",
		  "    ModInt& operator /= (const T rhs) { return *this *= ModInt(rhs).inverse(); }",
		  "",
		  "    ModInt& operator %= (const ModInt& rhs) { val %= rhs.val; return *this; }",
		  "    ModInt& operator %= (const T rhs) { val %= rhs; return *this; }",
		  "",
		  "    ModInt& operator ++() { return *this += 1; }",
		  "    ModInt& operator --() { return *this -= 1; }",
		  " ",
		  "    ModInt operator ++(T unused) { ModInt res(*this); ++*this; return res; }",
		  "    ModInt operator --(T unused) { ModInt res(*this); --*this; return res; }",
		  "    ",
		  "    ModInt operator + (const ModInt& rhs) const { ModInt res(*this); return res += rhs; }",
		  "    ModInt operator + (const T rhs) const { ModInt res(*this); return res += rhs; }",
		  "",
		  "    ModInt operator % (const ModInt& rhs) const { ModInt res(*this); return res %= rhs; }",
		  "    ModInt operator % (const T rhs) const { ModInt res(*this); return res %= rhs; }",
		  "",
		  "    ModInt operator - (const ModInt& rhs) const { ModInt res(*this); return res -= rhs; }",
		  "    ModInt operator - (const T rhs) const { ModInt res(*this); return res -= rhs; }",
		  "",
		  "    ModInt operator * (const ModInt& rhs) const { ModInt res(*this); return res *= rhs; }",
		  "    ModInt operator * (const T rhs) const { ModInt res(*this); return res *= rhs; }",
		  "",
		  "    ModInt operator / (const ModInt& rhs) const { ModInt res(*this); return res /= rhs; }",
		  "    ModInt operator / (const T rhs) const { ModInt res(*this); return res /= rhs; }",
		  "",
		  "    ModInt& operator = (const ModInt& rhs) { val = rhs.val; return *this; }",
		  "    ModInt& operator = (const T rhs) { val = rhs; return *this; }",
		  "",
		  "    T operator ~ () { return ~val; }",
		  "    bool operator ! () { return !val; }",
		  "",
		  "    bool operator == (const ModInt& rhs) const { return val == rhs.val; }",
		  "    bool operator == (const T rhs) const { return val == rhs; }",
		  "",
		  "    bool operator != (const ModInt& rhs) const { return val != rhs.val; }",
		  "    bool operator != (const T rhs) const { return val != rhs; }",
		  "",
		  "    bool operator < (const ModInt& rhs) const { return val < rhs.val; }",
		  "    bool operator < (const T rhs) const { return val < rhs; }",
		  "",
		  "    bool operator <= (const ModInt& rhs) const { return val <= rhs.val; }",
		  "    bool operator <= (const T rhs) const { return val <= rhs; }",
		  "",
		  "    bool operator > (const ModInt& rhs) const { return val > rhs.val; }",
		  "    bool operator > (const T rhs) const { return val > rhs; }",
		  "",
		  "    bool operator >= (const ModInt& rhs) const { return val >= rhs.val; }",
		  "    bool operator >= (const T rhs) const { return val >= rhs; }",
		  "",
		  "    T operator () () const { return val; }",
		  "",
		  "    ModInt inverse() const { return power(MOD - 2); }",
		  "",
		  "    ModInt power(T n) const {",
		  "        ModInt a = *this, res = 1;",
		  "        while (n > 0) {",
		  "            if (n & 1) res *= a;",
		  "            a *= a, n >>= 1;",
		  "        }",
		  "        return res;",
		  "    }",
		  "",
		  "    ModInt power(ModInt n) const {",
		  "        ModInt a = *this, res = 1;",
		  "        T e = n();",
		  "        while (e > 0) {",
		  "            if (e & 1) res *= a;",
		  "            a *= a, e >>= 1;",
		  "        }",
		  "        return res;",
		  "    }",
		  "",
		  "    friend ModInt operator ^ (ModInt rhs, T n) { return rhs.power(n); }",
		  "    friend ModInt operator ^ (ModInt rhs, ModInt n) { return rhs.power(n); }",
		  "",
		  "    friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept { return is >> x.val; }",
		  "    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }",
		  "",
		  "};",
		  "using Mint = ModInt < 998244353 >;",
		  ""
		],
		"description": "ModInt"
	},
    "Monotonic_Stacks": {
		"prefix": "Monotonic_Stacks",
		"body": [
		  "struct Next_Prev_Element {",
		  "",
		  "    Next_Prev_Element(){ }",
		  "",
		  "    vector < ll > nextGreaterelement(vector < ll >& nums) {",
		  "        int n = nums.size();",
		  "        vector < ll > res(n);",
		  "        stack < int > st;",
		  "        for(int i = n - 1; i >= 1; i--){",
		  "            while(!st.empty() && nums[st.top()] <= nums[i]) st.pop();",
		  "            res[i] = (st.empty() ? n : st.top());",
		  "            st.push(i);",
		  "        }",
		  "        return res;",
		  "    }",
		  "    ",
		  "    vector < ll > prevGreaterelement(vector < ll >& nums) {",
		  "        int n = nums.size();",
		  "        vector < ll > res(n);",
		  "        stack < int > st;",
		  "        for(int i = 1; i < n; i++){",
		  "            while(!st.empty() && nums[st.top()] <= nums[i]) st.pop();",
		  "            res[i] = (st.empty() ? 0 : st.top());",
		  "            st.push(i);",
		  "        }",
		  "        return res;",
		  "    }",
		  "",
		  "    vector < ll > nextSmallerelement(vector < ll >& nums) {",
		  "        int n = nums.size();",
		  "        vector < ll > res(n);",
		  "        stack < int > st;",
		  "        for(int i = n - 1; i >= 1; i--){",
		  "            while(!st.empty() && nums[st.top()] >= nums[i]) st.pop();",
		  "            res[i] = (st.empty() ? n : st.top());",
		  "            st.push(i);",
		  "        }",
		  "        return res;",
		  "    }",
		  "    ",
		  "    vector < ll > prevSmallerelement(vector < ll >& nums) {",
		  "        int n = nums.size();",
		  "        vector < ll > res(n);",
		  "        stack < int > st;",
		  "        for(int i = 1; i < n; i++){",
		  "            while(!st.empty() && nums[st.top()] >= nums[i]) st.pop();",
		  "            res[i] = (st.empty() ? 0 : st.top());",
		  "            st.push(i);",
		  "        }",
		  "        return res;",
		  "    }",
		  "",
		  "};"
		],
		"description": "Monotonic_Stacks"
	},
    "Ordered_Multiset": {
		"prefix": "Ordered_Multiset",
		"body": [
		  "#include <bits/stdc++.h>",
		  "#include <ext/pb_ds/assoc_container.hpp>",
		  "#include <ext/pb_ds/tree_policy.hpp>",
		  "",
		  "using namespace std;",
		  "using namespace __gnu_pbds;",
		  "",
		  "template <typename K, typename V, typename Comp = std::less<K>>",
		  "using ordered_map = tree<K, V, Comp, rb_tree_tag, tree_order_statistics_node_update>;",
		  "template <typename K, typename Comp = std::less<K>>",
		  "using ordered_set = ordered_map<K, null_type, Comp>;",
		  "",
		  "template <typename K, typename V, typename Comp = std::less_equal<K>>",
		  "using ordered_multimap = tree<K, V, Comp, rb_tree_tag, tree_order_statistics_node_update>;",
		  "template <typename K, typename Comp = std::less_equal<K>>",
		  "using ordered_multiset = ordered_multimap<K, null_type, Comp>;",
		  "",
		  "#define cin_2d(vec, n, m) for(int i = 0; i < n; i++) for(int j = 0; j < m && cin >> vec[i][j]; j++);",
		  "#define cout_2d(vec, n, m) for(int i = 0; i < n; i++, cout << \"\\n\") for(int j = 0; j < m && cout << vec[i][j] << \" \"; j++);",
		  "#define fixed(n) fixed << setprecision(n)",
		  "#define ceil(n, m) (((n) / (m)) + ((n) % (m) ? 1 : 0))",
		  "#define fill(vec, value) memset(vec, value, sizeof(vec));",
		  "#define add_mod(a, b, m) (((a % m) + (b % m)) % m)",
		  "#define sub_mod(a, b, m) (((a % m) - (b % m) + m) % m)",
		  "#define mul_mod(a, b, m) (((a % m) * (b % m)) % m)",
		  "#define all(vec) vec.begin(), vec.end()",
		  "#define rall(vec) vec.rbegin(), vec.rend()",
		  "#define sz(x) int(x.size())",
		  "#define debug(x) cout << #x << \": \" << (x) << \"\\n\";",
		  "#define fi first",
		  "#define se second",
		  "#define ll long long",
		  "#define ull unsigned long long",
		  "#define Mod  1'000'000'007",
		  "#define OO 2'000'000'000",
		  "#define EPS 1e-9",
		  "#define PI acos(-1)",
		  "template < typename T = int > using Pair = pair < T, T >;",
		  "vector < string > RET = {\"NO\", \"YES\"};",
		  "",
		  "template < typename T = int > istream& operator >> (istream &in, vector < T > &v) {",
		  "    for (auto &x : v) in >> x;",
		  "    return in;",
		  "}",
		  "",
		  "template < typename T = int > ostream& operator << (ostream &out, const vector < T > &v) { ",
		  "    for (const T &x : v) out << x << ' '; ",
		  "    return out;",
		  "}",
		  "",
		  "template < typename T = int , typename CompFunction = std::less_equal < T > > struct Ordered_Multiset {",
		  "    ",
		  "    ordered_multiset < T, CompFunction > mst;",
		  "    int Mode;",
		  "",
		  "    // Constructor ",
		  "    Ordered_Multiset(bool isSmaller = true) {",
		  "        mst.clear();",
		  "        Mode = !isSmaller ? 1 : -1;",
		  "    }",
		  "    ",
		  "    // Constructor with vector",
		  "    Ordered_Multiset(vector < T > &vec, bool isSmaller = true) {",
		  "        mst.clear();",
		  "        for (auto &x : vec) ",
		  "            mst.insert(x);",
		  "        Mode = !isSmaller ? 1 : -1;",
		  "    }",
		  "",
		  "    // Insert element",
		  "    void insert(T val) {",
		  "        mst.insert(val);",
		  "    }",
		  "",
		  "    // check if element exists or not",
		  "    bool is_exist(T val){ ",
		  "        if((mst.upper_bound(val)) == mst.end())",
		  "            return false;",
		  "        return ((*mst.upper_bound(val)) == val);",
		  "    }",
		  "",
		  "    // erase element if exists",
		  "    void erase(T val){",
		  "        if(is_exist(val))",
		  "            mst.erase(mst.upper_bound(val));",
		  "    }",
		  "    ",
		  "    // return element with given index",
		  "    T at(int idx){",
		  "        return (*mst.find_by_order(idx));",
		  "    }",
		  "",
		  "    // return element with given index like mst[idx]",
		  "    T operator [] (int idx){",
		  "        return at(idx);",
		  "    }",
		  "",
		  "    // return first index of element",
		  "    int first_idx(T val){ ",
		  "        if(!is_exist(val))",
		  "            return -1;",
		  "        return (mst.order_of_key(val));",
		  "    }",
		  "",
		  "    // return last index of element",
		  "    int last_idx(T val){",
		  "        if(!is_exist(val))",
		  "            return -1;",
		  "        if(at(sz(mst) - 1) == val)",
		  "            return sz(mst) -1;",
		  "        return first_idx(*mst.lower_bound(val)) - 1;",
		  "    }",
		  "",
		  "    // return number of occurences of element",
		  "    T count(T val){ ",
		  "        if(!is_exist(val))",
		  "            return 0;",
		  "        return last_idx(val) - first_idx(val) + 1;",
		  "    }",
		  "",
		  "    // clear the ordered multiset",
		  "    void clear(){",
		  "        mst.clear();",
		  "    }",
		  "",
		  "    // return size of ordered multiset",
		  "    int size(){",
		  "        return sz(mst);",
		  "    }",
		  "",
		  "    // return number of elements < Comp > of val",
		  "    int order_of_key(T val){",
		  "        return mst.order_of_key(val - Mode);",
		  "    }",
		  "",
		  "    // return iterator to element with given index",
		  "    typename ordered_multiset < T, CompFunction >::iterator find_by_order(int idx){",
		  "        return mst.find_by_order(idx);",
		  "    }",
		  "",
		  "    // print the ordered multiset",
		  "    friend ostream& operator << (ostream &out, const Ordered_Multiset < T, CompFunction > &mst) { ",
		  "        for (const T &x : mst.mst) out << x << ' '; ",
		  "        return out;",
		  "    }",
		  "",
		  "    // Ordered_Multiset < int, less_equal < int > > mst;",
		  "    // Ordered_Multiset < int, greater_equal < int > > mst;",
		  "",
		  "};",
		  "",
		  "",
		  "void Solve(){",
		  "    ",
		  "}",
		  "",
		  "int main(){",
		  "    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);",
		  "    int t = 1;",
		  "    // cin >> t;",
		  "    while(t--)",
		  "        Solve();",
		  "    return 0;",
		  "}"
		],
		"description": "Ordered_Multiset"
	},
    "Partial_2D": {
		"prefix": "Partial_2D",
		"body": [
		  "template < typename T = int > struct Partial_2D {",
		  "",
		  "    vector < vector < T > > partial;",
		  "    int n, m;",
		  "",
		  "    Partial_2D(int N, int M){",
		  "        n = N, m = M;",
		  "        partial.assign(n + 5, vector < T > (m + 5));",
		  "    }",
		  "",
		  "    void build_partial(int queries){",
		  "        while(queries--){",
		  "            int x1, y1, x2, y2, k = 1;",
		  "            cin >> x1 >> y1 >> x2 >> y2;",
		  "            if(x1 > x2) swap(x1, x2);",
		  "            if(y1 > y2) swap(y1, y2);",
		  "            partial[x2][y2] += k, partial[x2][y1 - 1] -= k; ",
		  "            partial[x1 - 1][y2] -= k, partial[x1 - 1][y1 - 1] += k;",
		  "        }",
		  "        for(int i = n; i >= 0; i--)",
		  "            for(int j = m; j >= 0; j--)",
		  "                partial[i][j] += partial[i][j + 1];",
		  "        for(int i = n; i >= 0; i--)",
		  "            for(int j = m; j >= 0; j--)",
		  "                partial[i][j] += partial[i + 1][j];",
		  "    }",
		  "",
		  "    T get(int x, int y){",
		  "        return partial[x][y];",
		  "    }",
		  "",
		  "    void print(){",
		  "        for(int i = 1; i <= n; i++, cout << \"\\n\")",
		  "            for(int j = 1; j <= m && cout << partial[i][j] << \" \"; j++);",
		  "    }",
		  "",
		  "};",
		  ""
		],
		"description": "Partial_2D"
	},
    "Power_Inverse": {
		"prefix": "Power_Inverse",
		"body": [
		  "template < typename T = int > struct Power_Inverse {",
		  "    ",
		  "    T n, r, mod;",
		  "    vector < T > fact, inv;",
		  "",
		  "    T fast_power(T b, T e, T MOD){",
		  "        T power = 1;",
		  "        while(e){",
		  "            if(e & 1) power = mod_combine(power, b, MOD);",
		  "            e >>= 1, b = mod_combine(b, b, MOD);",
		  "        }",
		  "        return power % MOD;",
		  "    }",
		  "",
		  "    T Inverse(T N, T MOD){",
		  "        return fast_power(N, MOD - 2, MOD) % MOD;",
		  "    }",
		  "",
		  "    Power_Inverse(T N, T R, T MOD){",
		  "        n = N, r = R, mod = MOD;",
		  "        fact.assign(n + 10, 1), inv.resize(n + 10, 1);",
		  "        for(ll i = 1; i <= n; i++){",
		  "            fact[i] = mod_combine(fact[i - 1], i, mod);",
		  "            inv[i] = Inverse(fact[i], mod);",
		  "        }",
		  "    }",
		  "",
		  "    // Combination",
		  "",
		  "    T nCr(){",
		  "        if(r > n) return 0ll;",
		  "        return (((fact[n] % mod) * (inv[r] % mod) % mod) * (inv[n - r] % mod)) % mod;",
		  "    }",
		  "",
		  "    // Permutation",
		  "",
		  "    T nPr(){",
		  "        if(r > n) return 0ll;",
		  "        return ((fact[n] % mod) * (inv[r] % mod)) % mod;",
		  "    }",
		  "",
		  "};"
		],
		"description": "Power_Inverse"
	},
    "Prefix_2D": {
		"prefix": "Prefix_2D",
		"body": [
		  "template < typename T = int > struct Prefix_2D {",
		  "",
		  "    int n, m;",
		  "    vector < vector < T > > prefix;",
		  "    ",
		  "    Prefix_2D(int N = 0, int M = 0){",
		  "        n = N, m = M;",
		  "        prefix.assign(n + 5, vector < T > (m + 5));",
		  "    }",
		  "",
		  "    // Get the sum of the number in the rectangle between x1, y1, x2, y2",
		  "",
		  "    T Get_Query(int x1, int y1, int x2, int y2){",
		  "        if(x1 > x2) swap(x1, x2);",
		  "        if(y1 > y2) swap(y1, y2);",
		  "        return prefix[x2][y2] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1] + prefix[x1 - 1][y1 - 1];",
		  "    }",
		  "",
		  "    void Build_Prefix(vector < vector < T > >& matrix){",
		  "        for(int i = 1; i <= n; i++)",
		  "            for(int j = 1; j <= m; j++)",
		  "                prefix[i][j] = matrix[i - 1][j - 1] + prefix[i][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1];",
		  "    }",
		  "",
		  "    void Print_Prefix(){",
		  "        for(int i = 1; i <= n; i++, cout << '\\n')",
		  "            for(int j = 1; j <= m && cout << prefix[i][j] << ' '; j++);",
		  "    }",
		  "    ",
		  "};"
		],
		"description": "Prefix_2D"
	},
    "Prim": {
		"prefix": "Prim",
		"body": [
		  "struct Prim {",
		  "",
		  "    struct Edge {",
		  "",
		  "        ll v, w;",
		  "",
		  "        Edge(ll V = 0, ll W = 0) : v(V), w(W) {}",
		  "",
		  "        bool operator < (const Edge &e) const {",
		  "            return w < e.w;",
		  "        }",
		  "",
		  "    };",
		  "",
		  "    vector < vector < Edge > > adj;",
		  "    vector < ll > marked;",
		  "",
		  "    Prim(ll n = 0){",
		  "        adj = vector < vector < Edge > > (n + 10);",
		  "        marked = vector < ll > (n + 10, 0);",
		  "    }",
		  "",
		  "    void build_adj(int edges, bool is_directed = false){",
		  "        for(int i = 0, u, v, w; i < edges && cin >> u >> v >> w; i++){",
		  "            adj[u].push_back(Edge(v, w));",
		  "            if(!is_directed)",
		  "                adj[v].push_back(Edge(u, w));",
		  "        }",
		  "    }",
		  "",
		  "    ll get_cost(int root){",
		  "        ll cost = 0;",
		  "        priority_queue < Edge > pq;",
		  "        pq.push(Edge(root, 0));",
		  "        while(!pq.empty()){",
		  "            auto [u, curr_cost] = pq.top();",
		  "            pq.pop();",
		  "            // Checking for cycle",
		  "            if(marked[u]) continue;",
		  "            marked[u] = true;",
		  "            cost += curr_cost;",
		  "            for(auto& [v, w] : adj[u]){",
		  "                if(!marked[v])",
		  "                    pq.push(Edge(v, w));",
		  "            }",
		  "        }",
		  "        return cost;",
		  "    }",
		  "",
		  "};"
		],
		"description": "Prim"
	},
    "Monotonic_Queue": {
		"prefix": "Monotonic_Queue",
		"body": [
		  "template < typename T = int > struct Monotonic_Stack {",
		  "    ",
		  "    vector < T > st, Monotonic;",
		  "    T DEFAULT = 0;",
		  "",
		  "    Monotonic_Stack() {",
		  "        Monotonic = { DEFAULT }, st = { };",
		  "    }",
		  "",
		  "    static T operation(T a, T b){",
		  "        return max(a, b);",
		  "    }",
		  "",
		  "    void push(T x){",
		  "        st.emplace_back(x);",
		  "        Monotonic.push_back(operation(Monotonic.back(), x));",
		  "    }",
		  "",
		  "    T pop(){",
		  "        T res = st.back();",
		  "        st.pop_back();",
		  "        Monotonic.pop_back();",
		  "        return res;",
		  "    }",
		  "    ",
		  "    bool empty(){",
		  "        return st.empty();",
		  "    }",
		  "    ",
		  "    T top(){",
		  "        return st.back();",
		  "    }",
		  "",
		  "    T Monotonic_val(){",
		  "        return Monotonic.back();",
		  "    }",
		  "",
		  "    int size(){",
		  "        return st.size();",
		  "    }",
		  "",
		  "};",
		  "",
		  "template < typename T = int > struct Monotonic_Queue {",
		  "",
		  "    Monotonic_Stack < T > s1, s2;",
		  "",
		  "    Monotonic_Queue () {",
		  "        s1 = Monotonic_Stack < T > (), s2 = Monotonic_Stack < T > ();",
		  "    }",
		  "",
		  "    void push(T x){",
		  "        s2.push(x);",
		  "    }",
		  "",
		  "    void pop(){",
		  "        if(s1.empty()){",
		  "            while(!s2.empty())",
		  "                s1.push(s2.pop());",
		  "        }",
		  "        s1.pop();",
		  "    }",
		  "",
		  "    T monotonic_val(){",
		  "        return Monotonic_Stack < T > ::operation(s1.Monotonic_val(), s2.Monotonic_val());",
		  "    }",
		  "",
		  "    bool is_good(){",
		  "        return monotonic_val() == 1;",
		  "    }",
		  "",
		  "    bool empty(){",
		  "        return s1.empty() && s2.empty();",
		  "    }",
		  "",
		  "    int size(){",
		  "        return s1.size() + s2.size();",
		  "    }",
		  "",
		  "};"
		],
		"description": "Monotonic_Queue"
	},
	"Segment_Tree": {
		"prefix": "Segment_Tree",
		"body": [
			"template < typename treeType = int, typename numsType = int, int Base = 0 >",
			"class Segment_Tree {",
			"private:",
			"    int size, max_level;",
			"    treeType DEFAULT;",
			"    vector < treeType > tree;",
			"    const function < treeType(const treeType&, const treeType&) > operation;",
			"",
			"    // Build the segment tree",
			"    void build(const vector < numsType >& nums, int idx, int lx, int rx) {",
			"        if (Base ? lx >= int(nums.size()) : lx > int(nums.size())) return;",
			"        if (rx == lx) tree[idx] = treeType(nums[lx - !Base]);",
			"        else {",
			"            int mx = (rx + lx) / 2;",
			"            build(nums, idx * 2, lx, mx);",
			"            build(nums, idx * 2 + 1, mx + 1, rx);",
			"            tree[idx] = operation(tree[idx * 2], tree[idx * 2 + 1]);",
			"        }",
			"    }",
			"",
			"    // Update the segment tree",
			"    void update(int index, numsType value, int idx, int lx, int rx) {",
			"        if (rx == lx) tree[idx] = treeType(value);",
			"        else {",
			"            int mx = (rx + lx) / 2;",
			"            if (index <= mx) update(index, value, idx * 2, lx, mx);",
			"            else update(index, value, idx * 2 + 1, mx + 1, rx);",
			"            tree[idx] = operation(tree[idx * 2], tree[idx * 2 + 1]);",
			"        }",
			"    }",
			"",
			"    // Query the segment tree",
			"    treeType query(int l, int r, int idx, int lx, int rx) const {",
			"        if (lx > r || l > rx) return DEFAULT;",
			"        if (lx >= l && rx <= r) return tree[idx];",
			"        int mx = (lx + rx) / 2;",
			"        return operation(query(l, r, idx * 2, lx, mx), query(l, r, idx * 2 + 1, mx + 1, rx));",
			"    }",
			"",
			"public:",
			"",
			"    Segment_Tree(",
			"        int n = 0, ",
			"        const vector < numsType >& nums = vector < numsType >(), ",
			"        const function < treeType(const treeType&, const treeType&) >& op = [](const treeType& a, const treeType& b) { return a + b; },",
			"        treeType def = 0",
			"    ) : size(1), max_level(1), DEFAULT(def), operation(op) {",
			"        while (size < n) size *= 2, max_level++;",
			"        tree = vector < treeType > (2 * size, DEFAULT);",
			"        if (!nums.empty()) build(nums, 1, 1, size);",
			"    }",
			"",
			"    void build(const vector < numsType >& nums) {",
			"        build(nums, 1, 1, size);",
			"    }",
			"",
			"    void update(int index, numsType value) {",
			"        update(index, value, 1, 1, size);",
			"    }",
			"",
			"    treeType query(int l, int r) const {",
			"        return query(l, r, 1, 1, size);",
			"    }",
			"",
			"    treeType operator[](int index) const {",
			"        return query(index, index, 1, 1, size);",
			"    }",
			"",
			"    // Print the segment tree as a pretty tree structure",
			"    void print() const {",
			"        if (tree.size() <= 1) return;",
			"        int level = 0;",
			"        queue < pair < int, int > > q;  // pair of (index in tree, level in tree)",
			"        q.push({1, level});",
			"        while (!q.empty()) {",
			"            int nodesAtCurrentLevel = q.size();",
			"            int spacesBetween = (1 << (max_level - level + 1)) - 1;",
			"            int leadingSpaces = (1 << (max_level - level)) - 1;",
			"            cout << string(leadingSpaces * 2, ' ');  // leading spaces for the first node in the level",
			"            while (nodesAtCurrentLevel--) {",
			"                auto [idx, lvl] = q.front();",
			"                q.pop();",
			"                cout << setw(2) << tree[idx];",
			"                // Print spaces between nodes at the current level",
			"                if (nodesAtCurrentLevel) cout << string(spacesBetween * 2, ' ');",
			"                // Add children to the queue",
			"                if (idx * 2 < tree.size()) {",
			"                    q.push({idx * 2, lvl + 1});",
			"                    q.push({idx * 2 + 1, lvl + 1});",
			"                }",
			"            }",
			"            cout << \"\\n\";  // new line for the new level",
			"            level++;",
			"        }",
			"    }",
			"};",
			""
		],
		"description": "Segment_Tree"
	},
    "Seive": {
		"prefix": "Seive",
		"body": [
		  "template < typename T = int > struct Seive {",
		  "",
		  "    vector < bool > is_prime;",
		  "    vector < T > primes;",
		  "",
		  "    Seive(int n){",
		  "        is_prime.assign(n + 1, true);",
		  "        is_prime[0] = is_prime[1] = false;",
		  "        for(ll i = 2; i <= sqrt(n); i++)",
		  "            if(is_prime[i])",
		  "                for(ll j = i * i; j <= n; j += i) is_prime[j] = false;",
		  "    }",
		  "",
		  "    // Build vector with prime numbers",
		  "",
		  "    void get_primes(int n){",
		  "        for(int i = 1; i <= n; i++)",
		  "            if(is_prime[i])",
		  "                primes.push_back(i);",
		  "    }",
		  "",
		  "    // Print the prime numbers",
		  "",
		  "    void print_primes(){",
		  "        for(auto& p : primes)",
		  "            cout << p << \" \";",
		  "        cout << \"\\n\";",
		  "    }",
		  "",
		  "};"
		],
		"description": "Seive"
	},
	"Sparse_Table": {
		"prefix": "Sparse_Table",
		"body": [
			"template < typename Tabletype = int, typename numsType = int, int Base = 0 > ",
			"class Sparse_Table {",
			"private:",
			"",
			"    int n, LOG;",
			"    vector < vector < Tabletype > > table;",
			"    vector < int > Bin_Log;",
			"    function < Tabletype(const Tabletype&, const Tabletype&) > operation;",
			"    Tabletype DEFAULT;",
			"",
			"    void Build_Table(){",
			"        for(int log = 1; log < LOG; log++)",
			"            for(int i = 1; i + (1 << log) - 1 <= n; i++)",
			"                table[i][log] = operation(table[i][log - 1], table[i + (1 << (log - 1))][log - 1]);",
			"    }",
			"",
			"    Tabletype query_1(int L, int R){",
			"        int log = Bin_Log[R - L + 1];",
			"        return operation(table[L][log], table[R - (1 << log) + 1][log]);",
			"    }",
			"",
			"    Tabletype query_log_n(int L, int R){",
			"        Tabletype answer = DEFAULT;",
			"        for (int log = LOG; log >= 0; log--){",
			"            if (L + (1 << log) - 1 <= R) {",
			"                answer = operation(answer, table[L][log]);",
			"                L += 1 << log;",
			"            }",
			"        }",
			"        return answer;",
			"    }",
			"",
			"public:",
			"",
			"    Sparse_Table(",
			"        int N = 0,",
			"        const vector < numsType >& vec = vector < numsType > (),",
			"        function < Tabletype(const Tabletype&, const Tabletype&) > op = [](const Tabletype& a, const Tabletype& b) { return min(a, b); },",
			"        Tabletype def = numeric_limits < Tabletype > ::max()",
			"    ): n(N), LOG(__lg(n) + 1), operation(op), DEFAULT(def) {",
			"        table = vector < vector < Tabletype > > (n + 10, vector < Tabletype > (LOG, DEFAULT));",
			"        Bin_Log = vector < int > (n + 10);",
			"        for(int i = 2; i <= n; i++)",
			"            Bin_Log[i] = Bin_Log[i >> 1] + 1;",
			"        for(int i = 1; i <= N; i++)",
			"            table[i][0] = Tabletype(vec[i - !Base]);",
			"        Build_Table();",
			"    }",
			"",
			"    Tabletype query(int L, int R, bool is_overlap = false){",
			"        return (!is_overlap ? query_1(L, R) : query_log_n(L, R));",
			"    }",
			"",
			"};",
			""
		],
		"description": "Sparse_Table"
	},
    "Binary_Trie": {
		"prefix": "Binary_Trie",
		"body": [
			"class Trie {",
			"public:",
			"    struct Node {",
			"        Node* child[2];",
			"        int freq;",
			"        ",
			"        Node() : freq(0) {",
			"            child[0] = child[1] = nullptr;",
			"        }",
			"    };",
			"",
			"    Node* root;",
			"    static constexpr int LOG = 30;",
			"",
			"    Trie() : root(new Node()) {}",
			"",
			"    void insert(int x) {",
			"        Node* curr = root;",
			"        for(int bit = LOG; bit >= 0; --bit) {",
			"            int bit_val = get_bit(x, bit);",
			"            if(!curr -> child[bit_val])",
			"                curr -> child[bit_val] = new Node();",
			"            curr = curr -> child[bit_val];",
			"            ++curr -> freq;",
			"        }",
			"    }",
			"",
			"    void erase(int x) {",
			"        if (search(x)) {",
			"            erase(x, LOG, root);",
			"        }",
			"    }",
			"",
			"    bool search(int x) const {",
			"        Node* curr = root;",
			"        for(int bit = LOG; bit >= 0; --bit) {",
			"            int bit_val = get_bit(x, bit);",
			"            if(!curr -> child[bit_val]) {",
			"                return false;",
			"            }",
			"            curr = curr -> child[bit_val];",
			"        }",
			"        return true;",
			"    }",
			"    ",
			"private:",
			"    void erase(int x, int bit, Node* curr) {",
			"        if(bit < 0) return;",
			"        int bit_val = get_bit(x, bit);",
			"        if (curr -> child[bit_val]) {",
			"            erase(x, bit - 1, curr -> child[bit_val]);",
			"            if (--curr -> child[bit_val] -> freq == 0) {",
			"                delete curr -> child[bit_val];",
			"                curr -> child[bit_val] = nullptr;",
			"            }",
			"        }",
			"    }",
			"",
			"    inline int get_bit(int x, int bit) const {",
			"        return (x >> bit) & 1;",
			"    }",
			"};"
		],
		"description": "Binary_Trie"
	},
	"Coordinate_Compression": {
		"prefix": "Coordinate_Compression",
		"body": [
		  "template < typename T = int > struct Coordinate_Compression {",
		  "",
		  "    vector < T > compressed;",
		  "    bool is_build = true;",
		  "",
		  "    Coordinate_Compression(){}",
		  "",
		  "    Coordinate_Compression(vector < T > &vec) {",
		  "        compressed = vec;",
		  "        build();",
		  "    }",
		  "",
		  "    void add(T x) {",
		  "        compressed.push_back(x);",
		  "        is_build = false;",
		  "    }",
		  "",
		  "    void build() {",
		  "        sort(all(compressed));",
		  "        compressed.resize(unique(all(compressed)) - compressed.begin());",
		  "        is_build = true;",
		  "    }",
		  "",
		  "    T get(T x) {",
		  "        if(!is_build) build();",
		  "        return upper_bound(all(compressed), x) - compressed.begin();",
		  "    }",
		  "",
		  "    vector < T > get_compressed(vector < T > &vec) {",
		  "        if(!is_build) build();",
		  "        vector < T > ret;",
		  "        for (auto &x : vec) ",
		  "            ret.push_back(get(x));",
		  "        return ret;",
		  "    }",
		  "",
		  "    vector < T > get_mapping(vector < T > &vec) {",
		  "        if(!is_build) build();",
		  "        vector < T > ret(sz(compressed) + 5);",
		  "        for (auto &x : vec)",
		  "            ret[get(x)] = x;",
		  "        return ret;",
		  "    }",
		  "",
		  "    int size(){",
		  "        if(!is_build) build();",
		  "        return sz(compressed);",
		  "    }",
		  "",
		  "};"
		],
		"description": "Coordinate_Compression"
	},
	"Converx_Hull": {
		"prefix": "Converx_Hull",
		"body": [
		  "template < typename T = int > struct Point {",
		  "    T x, y;",
		  "    Point(T _x = 0, T _y = 0) : x(_x), y(_y) {}",
		  "    Point(const Point &p) : x(p.x), y(p.y) {}",
		  "    Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }",
		  "    Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }",
		  "    Point operator * (T c) const { return Point(x * c, y * c); }",
		  "    Point operator / (T c) const { return Point(x / c, y / c); }",
		  "    bool operator == (const Point &p) const { return x == p.x && y == p.y; }",
		  "    bool operator != (const Point &p) const { return x != p.x || y != p.y; }",
		  "    bool operator < (const Point &p) const { return make_pair(y, x) < make_pair(p.y, p.x); }",
		  "    bool operator > (const Point &p) const { return make_pair(y, x) > make_pair(p.y, p.x); }",
		  "    bool operator <= (const Point &p) const { return make_pair(y, x) <= make_pair(p.y, p.x); }",
		  "    bool operator >= (const Point &p) const { return make_pair(y, x) >= make_pair(p.y, p.x); }",
		  "    friend istream& operator >> (istream &in, Point &p) { return in >> p.x >> p.y; }",
		  "    friend ostream& operator << (ostream &out, const Point &p) { return out << p.x << ' ' << p.y; }",
		  "    T dot(const Point &p) const { return x * p.x + y * p.y; }",
		  "    T cross(const Point &p) const { return x * p.y - y * p.x; }",
		  "    T cross(const Point &a, const Point &b) const { return (a - *this).cross(b - *this); }",
		  "    T dist() const { return x * x + y * y; }",
		  "    T dist(const Point &p) const { return (*this - p).dist(); }",
		  "    double distance() const { return sqrt(1.0 * dist()); }",
		  "    double distance(const Point &p) const { return sqrt(1.0 * dist(p)); }",
		  "    double angle() const { return atan2(y, x); }",
		  "    double angle(const Point &p) const { return atan2(cross(p), dot(p)); }",
		  "    Point unit() const { return *this / dist(); }",
		  "    Point perp() const { return Point(-y, x); }",
		  "    Point rotate(double a) const { return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); }",
		  "    Point rotate(const Point &p, double a) const { return (*this - p).rotate(a) + p; }",
		  "    Point normal() const { return perp().unit(); }",
		  "};",
		  "template < typename T = int > struct Converx_Hull {",
		  "",
		  "    typedef Point < T > point;",
		  "",
		  "    // Returns the orientation of the point c with respect to the line a-b",
		  "    int orientation(const point& a, const point& b, const point& c) {",
		  "        T val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);",
		  "        if(val < 0) return -1; // clockwise",
		  "        if(val > 0) return 1; // counter-clockwise",
		  "        return 0; // collinear",
		  "    }",
		  "",
		  "    // Returns true if c is on the left side of the line a-b",
		  "    bool cw(const point& a, const point& b, const point& c, bool include_collinear) {",
		  "        int o = orientation(a, b, c);",
		  "        return o < 0 || (include_collinear && o == 0);",
		  "    }",
		  "",
		  "    // return if a-b-c are collinear",
		  "    bool is_collinear(const point& a, const point& b, const point& c) {",
		  "        return orientation(a, b, c) == 0;",
		  "    }",
		  "",
		  "    // Returns a list of points on the convex hull",
		  "    vector < point > Convex_Points;",
		  "",
		  "    Converx_Hull(vector < point > &points, bool include_collinear = false) {",
		  "        point p0 = *min_element(all(points));",
		  "        sort(all(points), [&](const point& a, const point& b) {",
		  "            int o = orientation(p0, a, b);",
		  "            if(o == 0) return p0.dist(a) < p0.dist(b);",
		  "            return o < 0;",
		  "        });",
		  "        // remove redundant points",
		  "        points.erase(unique(all(points)), points.end());",
		  "",
		  "        if(include_collinear){",
		  "            int idx = sz(points) - 1;",
		  "            // remove collinear points from the end",
		  "            while(idx > 0 && is_collinear(p0, points[idx], points.back())) idx--;",
		  "            reverse(points.begin() + idx + 1, points.end());",
		  "        }",
		  "        ",
		  "        for(const point& p : points) {",
		  "            while(sz(Convex_Points) > 1 && !cw(Convex_Points[sz(Convex_Points) - 2], Convex_Points.back(), p, include_collinear)) ",
		  "                Convex_Points.pop_back();",
		  "            Convex_Points.push_back(p);",
		  "        }",
		  "    }",
		  "};"
		],
		"description": "Converx_Hull"
	},
	"Centroid_Decomposition": {
		"prefix": "Centroid_Decomposition",
		"body": [
		  "template < typename T = int > struct Centroid_Decomposition {",
		  "",
		  "    int n, treeRoot;",
		  "    const vector < vector < T > > adj;",
		  "    vector < T > SubtreeSz, isCentroid;",
		  "",
		  "    // Initialize the Centroid Decomposition",
		  "    Centroid_Decomposition(int N, const vector <vector < T > > &G, int Root = 1) : adj(G){",
		  "        n = N, treeRoot = Root;",
		  "        SubtreeSz = isCentroid = vector < T > (n + 5, 0);",
		  "    }",
		  "",
		  "    // update subtree size of each node",
		  "    int updateSize(int u, int p = -1){",
		  "        SubtreeSz[u] = 1;",
		  "        for (int v : adj[u]) ",
		  "            if (v != p && !isCentroid[v]) ",
		  "                SubtreeSz[u] += updateSize(v, u);",
		  "        return SubtreeSz[u];",
		  "    }",
		  "",
		  "    // get centroid of subtree rooted at u",
		  "    int getCentroid(int u, int target, int p = -1){",
		  "        for(auto& v : adj[u]){",
		  "            if(v == p || isCentroid[v]) continue;",
		  "            if(SubtreeSz[v] * 2 > target) ",
		  "                return getCentroid(v, target, u);",
		  "        }",
		  "        return u;",
		  "    }",
		  "",
		  "    // decompose tree into centroid tree",
		  "    void Centroid(int u, int p = 0){",
		  "        int centroidPoint = getCentroid(u, updateSize(u));",
		  "        ",
		  "        // do something with centroid",
		  "",
		  "        isCentroid[centroidPoint] = true;",
		  "        for(auto& v : adj[centroidPoint]){",
		  "            if(isCentroid[v]) continue;",
		  "            Centroid(v, centroidPoint);",
		  "        }",
		  "    }",
		  "    ",
		  "    // call this function to decompose the tree",
		  "    void Decompose(){",
		  "        Centroid(treeRoot);",
		  "    }",
		  "",
		  "};"
		],
		"description": "Centroid_Decomposition"
	},
	"nextGreaterelement": {
		"prefix": "nextGreaterelement",
		"body": [
		  "template < typename T = int > vector < T > nextGreaterelement(vector < T >& nums) {",
		  "        int n = nums.size();",
		  "        vector < T > res(n);",
		  "        stack < int > st;",
		  "        for(int i = n - 1; i >= 0; i--){",
		  "            while(!st.empty() && nums[st.top()] <= nums[i]) st.pop();",
		  "            res[i] = (st.empty() ? n : st.top());",
		  "            st.push(i);",
		  "        }",
		  "        return res;",
		  "    }"
		],
		"description": "nextGreaterelement"
	},
	"prevGreaterelement": {
		"prefix": "prevGreaterelement",
		"body": [
		  "template < typename T = int > vector < T > prevGreaterelement(vector < T >& nums) {",
		  "        int n = nums.size();",
		  "        vector < T > res(n);",
		  "        stack < int > st;",
		  "        for(int i = 0; i < n; i++){",
		  "            while(!st.empty() && nums[st.top()] <= nums[i]) st.pop();",
		  "            res[i] = (st.empty() ? 0 : st.top());",
		  "            st.push(i);",
		  "        }",
		  "        return res;",
		  "    }"
		],
		"description": "prevGreaterelement"
	},
	"nextSmallerelement": {
		"prefix": "nextSmallerelement",
		"body": [
		  "template < typename T = int > vector < T > nextSmallerelement(vector < T >& nums) {",
		  "        int n = nums.size();",
		  "        vector < T > res(n);",
		  "        stack < int > st;",
		  "        for(int i = n - 1; i >= 0; i--){",
		  "            while(!st.empty() && nums[st.top()] >= nums[i]) st.pop();",
		  "            res[i] = (st.empty() ? n : st.top());",
		  "            st.push(i);",
		  "        }",
		  "        return res;",
		  "    }"
		],
		"description": "nextSmallerelement"
	},
	"prevSmallerelement": {
		"prefix": "prevSmallerelement",
		"body": [
		  "template < typename T = int > vector < T > prevSmallerelement(vector < T >& nums) {",
		  "        int n = nums.size();",
		  "        vector < T > res(n);",
		  "        stack < int > st;",
		  "        for(int i = 0; i < n; i++){",
		  "            while(!st.empty() && nums[st.top()] >= nums[i]) st.pop();",
		  "            res[i] = (st.empty() ? 0 : st.top());",
		  "            st.push(i);",
		  "        }",
		  "        return res;",
		  "    }"
		],
		"description": "prevSmallerelement"
	},
	"Hash": {
		"prefix": "Hash",
		"body": [
		  "template < typename T = long long , int Base = 0 > struct Hash {",
		  "    ",
		  "    int n;",
		  "    vector < T > pow1, pow2, h1, h2;",
		  "    const T p1 = 313, p2 = 1013;",
		  "    const T m1 = 1e9 + 7, m2 = 1e9 + 9;",
		  " ",
		  "    Hash(const string& s){",
		  "        n = s.size();",
		  "        h1 = h2 = pow1 = pow2 = vector < T > (n + 5);",
		  "",
		  "        // calulcate the powers",
		  "        pow1[0] = pow2[0] = 1;",
		  "        for(int i = 1; i <= n; i++) {",
		  "            pow1[i] = (pow1[i - 1] * p1) % m1;",
		  "            pow2[i] = (pow2[i - 1] * p2) % m2;",
		  "        }",
		  "",
		  "        // calculate the hashes",
		  "        h1[0] = h2[0] = 1;",
		  "        for(int i = 1; i <= n; i++) {",
		  "            h1[i] = (h1[i - 1] * p1 + s[i - !Base]) % m1;",
		  "            h2[i] = (h2[i - 1] * p2 + s[i - !Base]) % m2;",
		  "        }",
		  "    }",
		  "",
		  "    Hash(const vector < T >& vec){",
		  "        n = vec.size();",
		  "        h1 = h2 = pow1 = pow2 = vector < T > (n + 5);",
		  "        ",
		  "        // calulcate the powers",
		  "        pow1[0] = pow2[0] = 1;",
		  "        for(int i = 1; i <= n; i++) {",
		  "            pow1[i] = (pow1[i - 1] * p1) % m1;",
		  "            pow2[i] = (pow2[i - 1] * p2) % m2;",
		  "        }",
		  "",
		  "        // calculate the hashes",
		  "        h1[0] = h2[0] = 1;",
		  "        for(int i = 1; i <= n; i++) {",
		  "            h1[i] = (h1[i - 1] * p1 + vec[i - !Base]) % m1;",
		  "            h2[i] = (h2[i - 1] * p2 + vec[i - !Base]) % m2;",
		  "        }",
		  "    }",
		  "",
		  "    // get the hash of substring [i, j]",
		  "    pair < T, T > sub(int l, int r) {",
		  "        // first hash",
		  "        T F = h1[r];",
		  "        F -= h1[l - 1] * pow1[r - l + 1];",
		  "        F = ((F % m1) + m1) % m1;",
		  "        ",
		  "        // second hash",
		  "        T S = h2[r];",
		  "        S -= h2[l - 1] * pow2[r - l + 1];",
		  "        S = ((S % m2) + m2) % m2;",
		  "        ",
		  "        return {F, S};",
		  "    }",
		  " ",
		  "    // merge two substrings",
		  "    pair < T, T > merge_hash(int l1, int r1, int l2, int r2) {",
		  "        auto a = sub(l1, r1), b = sub(l2, r2);",
		  "        ll F = ((a.first * pow1[r2 - l2 + 1]) + b.first) % m1;",
		  "        ll S = ((a.second * pow2[r2 - l2 + 1]) + b.second) % m2;",
		  "        return {F, S};",
		  "    }",
		  " ",
		  "    // get the hash of the idx'th character",
		  "    pair < T, T > at(int idx){",
		  "        return sub(idx, idx);",
		  "    }",
		  "",
		  "    // check if two parts are equals",
		  "    bool equal(int l1, int r1, int l2, int r2) {",
		  "        return sub(l1, r1) == sub(l2, r2);",
		  "    }",
		  "",
		  "};"
		],
		"description": "Hash"
	},
	"MoTree": {
		"prefix": "MoTree",
		"body": [
			"template < typename T = int , bool VAL_ON_EDGE = false >",
			"class MoTree {",
			"public:",
			"    struct Query {",
			"        int l, r, k, lca, queryIdx;",
			"        int64_t ord;",
			"",
			"        Query(vector < T >& S, vector < T >& E, int L = 0, int R = 0, int QueryIdx = 0, int LCA = 0, int HilbertPow = 0) {",
			"            if (S[L] > S[R])",
			"                swap(L, R);",
			"            if (LCA == L)",
			"                l = S[L] + VAL_ON_EDGE, r = S[R], lca = -1, queryIdx = QueryIdx;",
			"            else",
			"                l = E[L], r = S[R], lca = LCA, queryIdx = QueryIdx;",
			"            calcOrder(HilbertPow);",
			"        }",
			"",
			"        void calcOrder(int hilbert_pow) {",
			"            ord = MoTree::hilbertOrder(l, r, hilbert_pow, 0);",
			"        }",
			"",
			"        bool operator < (const Query& rhs) const {",
			"            return ord < rhs.ord;",
			"        }",
			"    };",
			"",
			"    MoTree(int N, int M, vector < vector < int > >& G, vector < T >& V, int root = 1) : curr_l(1), curr_r(0), n(N), m(M), SqrtN(n / sqrt(m) + 1), timer(1), ans(0), answers(M), val(V), adj(G) {",
			"        LOG = calcLog(N);",
			"        helbertPow = calcHilbertPow(2 * N + 1);",
			"        nodeFreq = S = E = dep = vector < int > (n + 5);",
			"        FT = vector < int > (2 * n + 5);",
			"        anc = vector < vector < int > > (n + 5, vector < int > (LOG));",
			"",
			"        dfs(root);",
			"    }",
			"",
			"    static inline int64_t hilbertOrder(int x, int y, int pow, int rotate) {",
			"        if (pow == 0) return 0;",
			"        int hpow = 1 << (pow - 1);",
			"        int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);",
			"        seg = (seg + rotate) & 3;",
			"        const int rotateDelta[4] = {3, 0, 0, 1};",
			"        int nx = x & (x ^ hpow), ny = y & (y ^ hpow);",
			"        int nrot = (rotate + rotateDelta[seg]) & 3;",
			"        int64_t subSquareSize = int64_t(1) << (2 * pow - 2);",
			"        int64_t ordd = seg * subSquareSize;",
			"        int64_t add = hilbertOrder(nx, ny, pow - 1, nrot);",
			"        ordd += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);",
			"        return ordd;",
			"    }",
			"",
			"    void getData() {",
			"        for (int i = 0, u, v; i < m && cin >> u >> v; i++)",
			"            queries.emplace_back(S, E, u, v, i, getLCA(u, v), helbertPow);",
			"        process();",
			"    }",
			"",
			"    void process() {",
			"        sort(queries.begin(), queries.end());",
			"",
			"        // start with the first query",
			"        curr_l = queries[0].l, curr_r = queries[0].l - 1;",
			"",
			"        for (auto& q : queries) {",
			"            setRange(q);",
			"",
			"            // if lca is -1 then the two nodes are in the same subtree",
			"            if (~q.lca && !VAL_ON_EDGE) ",
			"                add(q.lca);",
			"            ",
			"            answers[q.queryIdx] = Mex.get_mex();",
			"            ",
			"            if (~q.lca && !VAL_ON_EDGE) ",
			"                remove(q.lca);",
			"        }",
			"    }",
			"",
			"    vector < T > getAnswers() const {",
			"        return answers;",
			"    }",
			"",
			"private:",
			"    int curr_l, curr_r, n, m, SqrtN, timer, LOG, helbertPow;",
			"    T ans;",
			"    vector < T > answers, val;",
			"    vector < int > dep, S, E, FT, nodeFreq;",
			"    vector < vector < int > > adj, anc;",
			"    vector < Query > queries;",
			"",
			"    void dfs(int u, int p = -1) {",
			"        S[u] = timer;",
			"        FT[timer++] = u;",
			"        for (auto& [v, w] : adj[u]) {",
			"            if (v == p) continue;",
			"            dep[v] = dep[u] + 1;",
			"            anc[v][0] = u;",
			"            for (int bit = 1; bit < LOG; bit++)",
			"                anc[v][bit] = anc[anc[v][bit - 1]][bit - 1];",
			"            val[v] = w;",
			"            dfs(v, u);",
			"        }",
			"        E[u] = timer;",
			"        FT[timer++] = u;",
			"    }",
			"",
			"    int kthAncestor(int u, int k) const {",
			"        if (dep[u] < k)",
			"            return -1;",
			"        for (int bit = LOG - 1; bit >= 0; bit--)",
			"            if (k & (1 << bit))",
			"                u = anc[u][bit];",
			"        return u;",
			"    }",
			"",
			"    int getLCA(int u, int v) const {",
			"        if (dep[u] < dep[v])",
			"            swap(u, v);",
			"        u = kthAncestor(u, dep[u] - dep[v]);",
			"        if (u == v)",
			"            return u;",
			"        for (int bit = LOG - 1; bit >= 0; bit--)",
			"            if (anc[u][bit] != anc[v][bit])",
			"                u = anc[u][bit], v = anc[v][bit];",
			"        return anc[u][0];",
			"    }",
			"",
			"    void setRange(Query& q) {",
			"        while (curr_l > q.l) operation(--curr_l);",
			"        while (curr_r < q.r) operation(++curr_r);",
			"        while (curr_l < q.l) operation(curr_l++);",
			"        while (curr_r > q.r) operation(curr_r--);",
			"    }",
			"",
			"    inline void add(int u){",
			"    ",
			"    }",
			"",
			"    inline void remove(int u){",
			"",
			"    }",
			"",
			"    inline void operation(int idx) {",
			"        int u = FT[idx];",
			"        nodeFreq[u] ^= 1;",
			"        if (nodeFreq[u] == 1) {",
			"            // add u to the path",
			"            add(u);",
			"        } else {",
			"            // remove u from the path",
			"            remove(u);",
			"        }",
			"    }",
			"",
			"    int calcLog(int max_n) const {",
			"        int log = 0;",
			"        while ((1 << log) <= max_n) log++;",
			"        return log;",
			"    }",
			"",
			"    int calcHilbertPow(int max_n) const {",
			"        int pow = 0;",
			"        while ((1 << pow) < max_n) pow++;",
			"        return pow;",
			"    }",
			"};",
			""
		],
		"description": "MoTree"
	},
	"Trie": {
		"prefix": "Trie",
		"body": [
			"enum class TrieMode { Lowercase, Uppercase, Digits };",
			"template < TrieMode Mode >",
			"class Trie {",
			"public:",
			"    Trie() : root(new Node()) {}",
			"",
			"    void insert(const string& word) {",
			"        Node* curr = root;",
			"        for (char c : word) {",
			"            int index = charToIndex(c);",
			"            if (!curr -> children[index]) ",
			"                curr -> children[index] = new Node();",
			"            curr = curr -> children[index];",
			"            curr -> freq++;",
			"        }",
			"        curr -> is_word = true;",
			"    }",
			"",
			"    bool search(const string& word) const {",
			"        const Node* curr = root;",
			"        for (char c : word) {",
			"            int index = charToIndex(c);",
			"            if (!curr -> children[index]) return false;",
			"            curr = curr -> children[index];",
			"        }",
			"        return curr -> is_word;",
			"    }",
			"",
			"    void erase(const string& word) {",
			"        erase(word, 0, root);",
			"    }",
			"",
			"    bool is_prefix(const string& word) const {",
			"        const Node* curr = root;",
			"        for (char c : word) {",
			"            int index = charToIndex(c);",
			"            if (!curr -> children[index]) return false;",
			"            curr = curr -> children[index];",
			"        }",
			"        return true;",
			"    }",
			"    ",
			"private:",
			"    inline static constexpr int charSize() {",
			"        switch (Mode) {",
			"            case TrieMode::Lowercase: return 26;",
			"            case TrieMode::Uppercase: return 26;",
			"            case TrieMode::Digits:    return 10;",
			"        }",
			"        return 0; // Should never reach here",
			"    }",
			"",
			"    inline static int charToIndex(char c) {",
			"        switch (Mode) {",
			"            case TrieMode::Lowercase: return c - 'a';",
			"            case TrieMode::Uppercase: return c - 'A';",
			"            case TrieMode::Digits:    return c - '0';",
			"        }",
			"        return -1; // Should never reach here",
			"    }",
			"",
			"    struct Node {",
			"        Node* children[charSize()] = {nullptr};",
			"        bool is_word = false;",
			"        int freq = 0;",
			"    };",
			"",
			"    Node* root;",
			"",
			"    void erase(const std::string& word, size_t idx, Node* curr) {",
			"        if (idx == word.size()) return curr -> is_word = false, void();",
			"        int index = charToIndex(word[idx]);",
			"        if (curr -> children[index]) {",
			"            erase(word, idx + 1, curr -> children[index]);",
			"            curr -> children[index] -> freq--;",
			"            if (curr -> children[index] -> freq == 0) {",
			"                delete curr -> children[index];",
			"                curr -> children[index] = nullptr;",
			"            }",
			"        }",
			"    }",
			"};"
		],
		"description": "Trie"
	},
	"Convex_Hull_Trick": {
		"prefix": "Convex_Hull_Trick",
		"body": [
		  "struct Line {",
		  "",
		  "    mutable ll m, c, p;",
		  "",
		  "    bool operator < (const Line &o) const { ",
		  "        return m < o.m; ",
		  "    }",
		  "",
		  "    bool operator < (ll x) const { ",
		  "        return p < x; ",
		  "    }",
		  "",
		  "    ll val(ll x) const { ",
		  "        return m * x + c; ",
		  "    }",
		  "};",
		  "",
		  "template < typename T = int, T Mode = -1 > class CHT : multiset < Line, less < > > {",
		  "private:",
		  "    ",
		  "    static constexpr T LLimit = numeric_limits < T > :: min(), RLimit = numeric_limits < T > :: max();",
		  "",
		  "    T div(T a, T b) { // floored division",
		  "        return a / b - ((a ^ b) < 0 && a % b);",
		  "    }",
		  "",
		  "    bool is_intersect(iterator x, iterator y) {",
		  "        if (y == end()) return x -> p = RLimit, 0;",
		  "        if (x -> m == y -> m) x -> p = (x -> c > y -> c ? RLimit : LLimit);",
		  "        else x -> p = div(y -> c - x -> c, x -> m - y -> m);",
		  "        return x -> p >= y -> p;",
		  "    }",
		  "",
		  "public:",
		  "    ",
		  "    void add(T m, T c) {",
		  "        m *= Mode, c *= Mode;",
		  "        auto z = insert({m, c, 0}), y = z++, x = y;",
		  "        while (is_intersect(y, z)) z = erase(z);",
		  "        if (x != begin() && is_intersect(--x, y)) is_intersect(x, y = erase(y));",
		  "        while ((y = x) != begin() && (--x) -> p >= y -> p) is_intersect(x, erase(y));",
		  "    }",
		  "",
		  "    T query(T x) {",
		  "        assert(!empty());",
		  "        auto l = *lower_bound(x);",
		  "        return Mode * l.val(x);",
		  "    }",
		  "",
		  "};"
		],
		"description": "Convex_Hull_Trick"
	},
	"PST": {
		"prefix": "PST",
		"body": [
		  "template < typename T = int , int Base = 0 > struct PST {",
		  " ",
		  "    struct Node {",
		  "       ",
		  "        T val, prefix;",
		  "        Node *left, *right;",
		  " ",
		  "        Node(T _val = 0) {",
		  "            this -> val = _val;",
		  "            this -> prefix = max(0ll, _val);",
		  "            left = right = this;",
		  "        }",
		  " ",
		  "        Node(Node* node, Node* l = new Node, Node* r = new Node) {",
		  "            val = node -> val;",
		  "            prefix = node -> prefix;",
		  "            left = l;",
		  "            right = r;",
		  "        }",
		  "    };",
		  " ",
		  "    vector < Node* > roots;",
		  "    T N, Lx, Rx;",
		  " ",
		  "    PST(int n = 0, T lx = -1e9, T rx = 1e9) : N(n), Lx(lx), Rx(rx) {",
		  "        roots = vector < Node* > (n + 5, new Node);",
		  "    }",
		  "",
		  "    Node* build(const vector < T >& nums, T l, T r){",
		  "        if(l == r) return new Node(nums[l - !Base]);",
		  "        T mx = l + (r - l) / 2;",
		  "        Node* L = build(nums, l, mx);",
		  "        Node* R = build(nums, mx + 1, r);",
		  "        return new Node(operation(L, R), L, R);",
		  "    }",
		  "",
		  "    void build(const vector < T >& nums){",
		  "        roots[0] = build(nums, Lx, Rx);",
		  "    }",
		  " ",
		  "    Node* operation(Node* a, Node* b){",
		  "        Node* Merged = new Node();",
		  "        Merged -> val = a -> val + b -> val;",
		  "        Merged -> prefix = max(a -> prefix, a -> val + b -> prefix);",
		  "        return Merged;",
		  "    }",
		  " ",
		  "    Node* update(Node* root, int idx, T val, T lx, T rx){",
		  "        if(idx < lx || idx > rx) return root;",
		  "        if(lx == rx) return new Node(val);",
		  "        T mx = lx + (rx - lx) / 2;",
		  "        Node* L = update(root -> left, idx, val, lx, mx);",
		  "        Node* R = update(root -> right, idx, val, mx + 1, rx);",
		  "        return new Node(operation(L, R), L, R);",
		  "    }",
		  "  ",
		  "    void insert(int idx, T val, int curr_time, int prev_time){",
		  "        roots[curr_time] = update(roots[prev_time], idx, val, Lx, Rx);",
		  "    }",
		  "",
		  "    void update(int idx, T val, int curr_time){",
		  "        roots[curr_time] = update(roots[curr_time], idx, val, Lx, Rx);",
		  "    }",
		  " ",
		  "    Node* query(Node* root, int l, int r, T lx, T rx){",
		  "        if (root == nullptr) return new Node(); // Base case for null pointer",
		  "        if (lx > r || l > rx) return new Node(); // Base case for out-of-range interval",
		  "        if(lx >= l && rx <= r) return root;",
		  "        int mx = (lx + rx) / 2;",
		  "        Node* L = query(root -> left, l, r, lx, mx);",
		  "        Node* R = query(root -> right, l, r, mx + 1, rx);",
		  "        return operation(L, R);",
		  "    }",
		  "    ",
		  "    T query(int l, int r, int time){",
		  "        return query(roots[time], l, r, Lx, Rx) -> prefix;",
		  "    }",
		  "",
		  "    T get(int time, int idx){",
		  "        return query(idx, idx, time) -> prefix;",
		  "    }",
		  "};"
		],
		"description": "PST"
	},
	"Miller_Rabin": {
		"prefix": "Miller_Rabin",
		"body": [
		  "template < typename T = long long , int Rounds = 10 > struct Miller_Rabin {",
		  "",
		  "    T BinMul(T b, T e, T mod) {",
		  "        T res = 0;",
		  "        while (e > 0) {",
		  "            if (e & 1)",
		  "                res = ((res % mod) + (b % mod)) % mod;",
		  "            e >>= 1;",
		  "            b = ((b % mod) + (b % mod)) % mod;",
		  "        }",
		  "        return res;",
		  "    }",
		  "",
		  "    T BinPow(T b, T e, T mod) {",
		  "        T res = 1;",
		  "        while (e > 0) {",
		  "            if (e & 1)",
		  "                res = BinMul(res, b, mod);",
		  "            e >>= 1;",
		  "            b = BinMul(b, b, mod);",
		  "        }",
		  "        return res;",
		  "    }",
		  "",
		  "    bool is_prime(T num){",
		  "        // Handling base cases:",
		  "        if(num < 2) return false;",
		  "        if(num != 2 && num % 2 == 0) return false;",
		  "",
		  "        // Now our num is odd number greater than 1",
		  "        T d = num - 1;",
		  "",
		  "        while (d % 2 == 0)",
		  "            d >>= 1;",
		  "        ",
		  "        for (int loop = 1; loop <= Rounds; loop++) {",
		  "            T a = rand() % (num - 1) + 1, temp = d;",
		  "            T x = BinPow(a, temp, num);",
		  "            while (temp != num - 1 && x != 1 && x != num - 1) {",
		  "                x = BinMul(x, x, num);",
		  "                temp <<= 1;",
		  "            }",
		  "            if (x != num - 1 && temp % 2 == 0)",
		  "                return false;",
		  "        }",
		  "        // If we reach here, then the number is prime",
		  "        return true; ",
		  "    }",
		  "",
		  "};"
		],
		"description": "Miller_Rabin"
	},
	"graph_rep": {
		"prefix": "graph_rep",
		"body": [
		  "// ----------------------------------------------------------- //",
		  "",
		  "#define adj_loop(u, v, e) for(int e = head[u], v; ~e && (v = edges[e].to, 1); e = edges[e].nxt)",
		  "",
		  "template < typename T = int > struct edgeData {",
		  "",
		  "    T to, nxt, cost;",
		  "",
		  "    edgeData(T TO = 0, T NXT = 0, T COST = 0) : to(TO), nxt(NXT), cost(COST) {}",
		  "",
		  "};",
		  "",
		  "int edge_count;",
		  "vector < edgeData < int > > edges;",
		  "vector < int > head;",
		  "",
		  "void init(int n, int m){",
		  "    edges = vector < edgeData < int > > (2 * m + 5);",
		  "    head = vector < int > (n + 5, -1);",
		  "    edge_count = 1;",
		  "}",
		  "",
		  "void addEdge(int u, int v, int c = 0){",
		  "    edges[edge_count].to = v;",
		  "    edges[edge_count].cost = c;",
		  "    edges[edge_count].nxt = head[u];",
		  "    head[u] = edge_count++;",
		  "}",
		  "",
		  "void AddBiEdge(int u, int v, int c = 0){",
		  "    addEdge(u, v, c);",
		  "    addEdge(v, u, c);",
		  "}",
		  "",
		  "// ----------------------------------------------------------- //",
		  ""
		],
		"description": "graph_rep"
	},
	"DP_Digits": {
		"prefix": "DP_Digits",
		"body": [
		  "ll dp[20][2][2][90], k;",
		  "string L, R;",
		  "",
		  "ll cnt_num(int idx = 0, bool not_smaller = true, bool not_greater = true, int sum = 0){",
		  "    if(idx == sz(L)) return !sum;",
		  "    ll &ret = dp[idx][not_smaller][not_greater][sum];",
		  "    if(~ret) return ret;",
		  "    int low = (not_smaller ? L[idx] - '0' : 0), high = (not_greater ? R[idx] - '0' : 9);",
		  "    ret = 0;",
		  "    for(int d = low; d <= high; d++)",
		  "        ret += cnt_num(idx + 1, not_smaller & (d == (L[idx] - '0')), not_greater & (d == (R[idx] - '0')), (sum + d) % k);",
		  "    return ret;",
		  "}",
		  "",
		  "void init(ll l, ll r){",
		  "    memset(dp, -1, sizeof(dp));",
		  "    L = to_string(l);",
		  "    R = to_string(r);",
		  "    if(sz(L) < sz(R))",
		  "        L = string(sz(R) - sz(L), '0') + L;",
		  "}",
		  ""
		],
		"description": "DP_Digits",
	},
	"Prime_Seive": {
		"prefix": "Prime_Seive",
		"body": [
		  "// Vector to store the smallest prime factor of numbers from 1 to N.",
		  "vector < int > SPF;",
		  "",
		  "// Vector to store prime factors of numbers from 1 to N.",
		  "vector < vector < int > > primeFactors;",
		  "",
		  "// Function to calculate prime factors of a number.",
		  "vector < int > PrimeFactors(int x){",
		  "    vector < int > ret;",
		  "    while(x > 1){",
		  "        ret.push_back(SPF[x]);",
		  "        x /= SPF[x];",
		  "    }",
		  "    return ret;",
		  "}",
		  "",
		  "// Function to calculate smallest prime factors of numbers from 1 to N using Sieve of Eratosthenes.",
		  "void Seive(int N){",
		  "    // Initializing vector SPF to store smallest prime factor of numbers from 1 to N.",
		  "    SPF = vector < int > (N + 5);",
		  "",
		  "    // Initializing vector primeFactors to store prime factors of numbers from 1 to N.",
		  "    primeFactors = vector < vector < int > > (N + 5);",
		  "",
		  "    // Initializing SPF vector with i for all numbers.",
		  "    for(int i = 1; i <= N; i++)",
		  "        SPF[i] = i;",
		  "",
		  "    // Updating SPF vector for even numbers.",
		  "    for(int i = 2; i <= N; i += 2)",
		  "        SPF[i] = 2;",
		  "",
		  "    // Updating SPF vector for odd numbers.",
		  "    for(int i = 3; i * i <= N; i++){",
		  "        if(SPF[i] == i){",
		  "            for(int j = i * i; j <= N; j += i)",
		  "                if(SPF[j] == j)",
		  "                    SPF[j] = i;",
		  "        }",
		  "    }",
		  "",
		  "    // Calculating prime factors of numbers from 1 to N.",
		  "    for(int i = 1; i <= N; i++)",
		  "        primeFactors[i] = PrimeFactors(i);",
		  "}"
		],
		"description": "Prime_Seive"
	},
	"Matrix_Power": {
		"prefix": "Matrix_Power",
		"body": [
		  "template < typename T = int , const T MOD = 1000000007, T N = 2 >  struct Matrix {",
		  "",
		  "    vector < vector < T > > Mat;",
		  "",
		  "    // add two elements",
		  "    static T add(const T& a, const T& b){",
		  "        return (a + b) % MOD;",
		  "    }",
		  "",
		  "    // multiplicatate two element",
		  "    static T mul(const T& a, const T& b){",
		  "        return ((a % MOD) * (b % MOD)) % MOD;",
		  "    }",
		  "",
		  "    // Constructor to fill the matrix with this value",
		  "    Matrix(T val = 0) {",
		  "        Mat.assign(N, vector < T > (N, val));",
		  "    }",
		  "",
		  "    // Constructor to make matrix with this 2D Vector",
		  "    Matrix(const vector < vector < T > > & b){",
		  "        Mat = b;",
		  "    }",
		  "",
		  "    // Overloaded the = operator",
		  "    Matrix& operator = (const Matrix& b){",
		  "        Mat = b.Mat;",
		  "        return *this;",
		  "    }",
		  "",
		  "    // Overloaded the = operator",
		  "    Matrix& operator = (const vector < vector < T > > & b){",
		  "        Mat = b;",
		  "        return *this;",
		  "    }",
		  "",
		  "    // Get Transition matrix",
		  "    static vector < vector < T > > GetTrans(){",
		  "        vector < vector < T > > Trans {",
		  "            {0, 1},",
		  "            {3, 2}",
		  "        };",
		  "        return Trans;",
		  "    }",
		  "",
		  "    // Get the identity matrix",
		  "    static vector < vector < T > > GetIdentity(){",
		  "        vector < vector < T > > Identity(N, vector < T > (N));",
		  "        for(int i = 0; i < N; i++)",
		  "            Identity[i][i] = 1;",
		  "        return Identity;",
		  "    }",
		  "",
		  "    // Get the zero matrix",
		  "    static vector < vector < T > > GetZero(){",
		  "        vector < vector < T > > Zero(N, vector < T > (N));",
		  "        return Zero;",
		  "    }",
		  "",
		  "    // Overload the [][] operator",
		  "    vector < T >& operator[](T index) {",
		  "        return Mat[index];",
		  "    }",
		  "",
		  "    // Overload the [][] operator",
		  "    const vector < T >& operator[](T index) const {",
		  "        return Mat[index];",
		  "    }",
		  "",
		  "    // Overload the * operator",
		  "    Matrix friend operator * (const Matrix& a, const Matrix& b){",
		  "        Matrix res = GetZero();",
		  "        for(int i = 0; i < N; i++)",
		  "            for(int j = 0; j < N; j++)",
		  "                for(int k = 0; k < N; k++)",
		  "                    res[i][j] = add(res[i][j], mul(a[i][k], b[k][j]));",
		  "        return res;",
		  "    }",
		  "",
		  "    // Overload the ^ operator",
		  "    Matrix friend operator ^ (Matrix b, ll e){",
		  "        Matrix Trans = GetTrans();",
		  "        while(e){",
		  "            if(e & 1) b *= Trans;",
		  "            Trans *= Trans;",
		  "            e >>= 1;",
		  "        }",
		  "        return b;",
		  "    }",
		  "",
		  "    // Overload the + operator",
		  "    Matrix friend operator + (const Matrix& a, const Matrix& b){",
		  "        Matrix res = GetZero();",
		  "        for(int i = 0; i < N; i++)",
		  "            for(int j = 0; j < N; j++)",
		  "                res[i][j] = add(a[i][j], b[i][j]);",
		  "        return res;",
		  "    }",
		  "",
		  "    // Overload the += operator",
		  "    Matrix friend operator += (Matrix& a, const Matrix& b){",
		  "        a = a + b;",
		  "        return a;",
		  "    }",
		  "",
		  "    // Overload the *= operator",
		  "    Matrix friend operator *= (Matrix& a, const Matrix& b){",
		  "        a = a * b;",
		  "        return a;",
		  "    }",
		  "",
		  "    // Overload the ^= operator",
		  "    Matrix friend operator ^= (Matrix& a, ll b){",
		  "        a = a ^ b;",
		  "        return a;",
		  "    }",
		  "",
		  "    // Get the n-th term",
		  "    T n_th(T n){",
		  "        if(n <= 1) return 0;",
		  "        Matrix < T >  Ans = GetTrans();",
		  "        Ans ^= (n - 1);",
		  "        return Ans[0][0];",
		  "    }",
		  "};"
		],
		"description": "Matrix_Power"
	},
	"Fenwick_Tree_Range": {
		"prefix": "Fenwick_Tree_Range",
		"body": [
		  "template < typename T = int > struct Fenwick_Tree_Range {",
		  "    ",
		  "    int N;",
		  "    T DEFAULT;",
		  "    vector < T > M, C;",
		  "",
		  "    Fenwick_Tree_Range(int sz = 0){",
		  "        N = sz + 1, DEFAULT = 0;",
		  "        M = C = vector < T > (N + 10);",
		  "    }",
		  "",
		  "    int lowest_bit(int idx){",
		  "        return (idx & -idx);",
		  "    }",
		  "",
		  "    void build(vector < T >& nums){",
		  "        for(int i = 0; i < sz(nums); i++)",
		  "            add(i, i, nums[i]);",
		  "    }",
		  "",
		  "    void add_range(int idx, T addM, T addC){",
		  "        idx++;",
		  "        while(idx <= N){",
		  "            M[idx] += addM;",
		  "            C[idx] += addC;",
		  "            idx += lowest_bit(idx);",
		  "        }",
		  "    }",
		  "",
		  "    void add(int l, int r, T val) {",
		  "        add_range(l, val, -val * (l - 1));",
		  "        add_range(r + 1, -val, val * r);",
		  "    }",
		  "",
		  "    T get(int idx){",
		  "        T ans = DEFAULT;",
		  "        int pos = idx++;",
		  "        while(idx){",
		  "            ans += pos * M[idx] + C[idx];",
		  "            idx -= lowest_bit(idx);",
		  "        }",
		  "        return ans;",
		  "    }",
		  "",
		  "    T query(int L, int R){",
		  "        if(L > R) return DEFAULT;",
		  "        return get(R) - get(L - 1);",
		  "    }",
		  "};",
		  ""
		],
		"description": "Fenwick_Tree_Range"
	},
	"Sqrt_Decomp": {
		"prefix": "Sqrt_Decomp",
		"body": [
		  "template < typename T = int, int Base = 0 > struct Sqrt_Decomp {",
		  "",
		  "    int n, len;",
		  "    vector < T > a; ",
		  "    vector < vector < T > > b;",
		  "    T U_Default, Q_Default;",
		  "",
		  "    // calculate the length of each block",
		  "    T calc_sq(int N){",
		  "        int sq = sqrt(N);",
		  "        return sq * sq == N ? sq : sq + 1;",
		  "    }",
		  "",
		  "    Sqrt_Decomp(int N = 0){",
		  "        n = N, len = calc_sq(n), U_Default = 0, Q_Default = 0;",
		  "        a = vector < T > (n + 5, U_Default);",
		  "        b = vector < vector < T > > (len + 5);",
		  "    }",
		  "",
		  "    Sqrt_Decomp(int N, const vector < T >& vec){",
		  "        n = N, len = calc_sq(n), U_Default = 0, Q_Default = 0;",
		  "        a = vec;",
		  "        b = vector < vector < T > > (len + 5);",
		  "        build();",
		  "    }",
		  "",
		  "    // build each block",
		  "    void build(){",
		  "        for(int i = 1; i <= n; i++)",
		  "            b[i / len].push_back(a[i - !Base]);",
		  "        for(int i = 0; i <= len; i++)",
		  "            sort(all(b[i]));",
		  "    }",
		  "",
		  "    // just update this index in the block O(1)",
		  "    void update(int idx, T val){",
		  "        int idx2 = lower_bound(all(b[idx / len]), a[idx - !Base]) - b[idx / len].begin();",
		  "        b[idx / len][idx2] = a[idx - !Base] = val;",
		  "        sort(all(b[idx / len]));",
		  "    }",
		  "",
		  "    // re-calculate the block again O(sqrt(n))",
		  "    void update_range(int idx, T val){",
		  "        a[idx - !Base] = val;",
		  "        b[idx / len].clear();",
		  "        for(int i = idx / len * len; i < min(n, (idx / len + 1) * len); i++)",
		  "            b[idx / len].push_back(a[i - !Base]);",
		  "        sort(all(b[idx / len]));",
		  "    }",
		  "",
		  "    // query on the range from L to R",
		  "    T query(int l, int r, T x){",
		  "        T res = Q_Default;",
		  "        while(l < r && l % len != 0)",
		  "            res += a[l++ - !Base] >= x;",
		  "        while(l + len <= r){",
		  "            res += sz(b[l / len]) - (lower_bound(all(b[l / len]), x) - b[l / len].begin());",
		  "            l += len;",
		  "        }",
		  "        while(l <= r)",
		  "            res += a[l++ - !Base] >= x;",
		  "        return res;",
		  "    }",
		  "",
		  "};"
		],
		"description": "Sqrt_Decomp"
	},
	"Hashed_Deque": {
		"prefix": "Hashed_Deque",
		"body": [
		"mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());",
		"",
		"struct Hashed_Deque {",
		"",
		"    int len;",
		"    vector < int > val; ",
		"    deque < int > curr;",
		"    // N is the larget size of the container",
		"    // base is the minimum prime number larger than the maximum value of the container",
		"    const int N = 5e5 + 5, base = 1e9 + 7;",
		"",
		"    Hashed_Deque(){",
		"        val = vector < int > (2);",
		"        curr.clear();",
		"        len = 0;",
		"        initial();",
		"    }",
		"",
		"    ll rand(ll l, ll r){",
		"        return uniform_int_distribution < ll >(l, r)(rng);",
		"    }",
		"",
		"    vector < ll > mod;",
		"    vector < vector < ll > > p, inv;",
		"",
		"    bool is_prime(ll x){",
		"        if(x < 2 || (x % 2 == 0 && x != 2)) return false;",
		"        for(int i = 3; i <= sqrt(x); i += 2)",
		"            if(x % i == 0) ",
		"                return false;",
		"        return true;",
		"    }",
		"",
		"    ll nxt_prime(ll x){",
		"        while(!is_prime(x)) x++;",
		"        return x;",
		"    }",
		"",
		"    void get_mods(){",
		"        mod[0] = nxt_prime(rand(9e8, 1e9 + 9));",
		"        mod[1] = nxt_prime(rand(9e8, 1e9 + 9));",
		"        while(mod[1] == mod[0])",
		"            mod[1] = nxt_prime(rand(9e8, 1e9 + 9));",
		"    }",
		"",
		"    ll fast_power(ll b, ll md){",
		"        ll e = md - 2, res = 1;",
		"        while(e) {",
		"            if(e & 1)",
		"                res = ((res % md) * (b % md)) % md;",
		"            b = ((b % md) * (b % md)) % md;",
		"            e >>= 1;",
		"        }",
		"        return res;",
		"    }",
		"",
		"    void initial(){",
		"        mod = vector < ll > (2);",
		"        p = inv = vector < vector < ll > > (N, vector < ll > (2, 1));",
		"        get_mods();",
		"        for(int i = 1; i < N;++i) ",
		"            for(int j = 0;j < 2; ++j){",
		"                p[i][j] = 1ll * p[i - 1][j] * base % mod[j];",
		"                inv[i][j] = fast_power(p[i][j], mod[j]);",
		"            }",
		"    }",
		"",
		"    void push_back(int x){",
		"        for(int i = 0; i < 2; ++i)",
		"            val[i] = (1ll * val[i] * base % mod[i] + x) % mod[i];",
		"        curr.push_back(x);",
		"        ++len;",
		"    }",
		"",
		"    void push_front(int x){",
		"        for(int i = 0; i < 2;++i)",
		"        val[i] = (1ll * x * p[len][i] % mod[i] + val[i]) % mod[i];",
		"        curr.push_front(x);",
		"        ++len;",
		"    }",
		"",
		"    void pop_back(){",
		"        for(int i = 0; i < 2; ++i){",
		"            val[i] = ((val[i] - curr.back()) % mod[i] +mod[i]) %mod[i];",
		"            val[i] = 1ll * val[i] * inv[1][i] % mod[i];",
		"        }",
		"        curr.pop_back();",
		"        --len;",
		"    }",
		"",
		"    void pop_front(){",
		"        --len ;",
		"        for(int i = 0; i < 2; ++i){",
		"            int v = 1ll * curr.front() * p[len][i] % mod[i];",
		"            val[i] = ((val[i] - v) % mod[i] + mod[i]) % mod[i];",
		"        }",
		"        curr.pop_front();",
		"    }",
		"",
		"    int size(){",
		"        return len;",
		"    }",
		"",
		"    bool operator ==(const Hashed_Deque &rhs){",
		"        return (rhs.len == len) && (rhs.val[0] == val[0]) && (rhs.val[1] == val[1]);",
		"    }",
		"",
		"};"
		],
		"description": "Hashed_Deque"
	},
	"tarjan": {
		"prefix": "tarjan",
		"body": [
		  "int timer;",
		  "vector < vector < int > > adj, comps;",
		  "vector < int > low_link, in_stack, node_idx, comp_idx;",
		  "stack < int > stk;",
		  "vector < Pair < int > > bridges;",
		  "set < int > art_points;",
		  "",
		  "void init(int n){",
		  "    timer = 0;",
		  "    adj = vector < vector < int > > (n + 5);",
		  "    low_link = node_idx = comp_idx = vector < int > (n + 5, -1);",
		  "    in_stack = vector < int > (n + 5, false);",
		  "    comps.clear();",
		  "    stk = stack < int > ();",
		  "}",
		  "",
		  "void tarjan(int u){",
		  "    in_stack[u] = true;",
		  "    low_link[u] = node_idx[u] = timer++;",
		  "    stk.push(u);",
		  "    for(auto& v : adj[u]){",
		  "        if(node_idx[v] == -1){",
		  "            tarjan(v);",
		  "            // minimize ancestor of my child",
		  "            low_link[u] = min(low_link[u], low_link[v]);",
		  "            // add bridge",
		  "            if(low_link[v] == node_idx[v])",
		  "                bridges.push_back({u, v});",
		  "            // add articulation point",
		  "            if(low_link[v] >= node_idx[u])",
		  "                art_points.insert(u);",
		  "        }else if(in_stack[v])",
		  "            low_link[u] = min(low_link[u], node_idx[v]);",
		  "    }",
		  "",
		  "    // head of SCC",
		  "    if(low_link[u] == node_idx[u]){",
		  "        comps.push_back(vector < int > ());",
		  "        int v = -1;",
		  "        while(v != u){",
		  "            v = stk.top();",
		  "            stk.pop();",
		  "            in_stack[v] = false; // remove from stack",
		  "            comps.back().push_back(v); // add node to current component",
		  "            comp_idx[v] = sz(comps) - 1; // set component index",
		  "        }",
		  "    }",
		  "}",
		  ""
		],
		"description": "tarjan"
	},
	"Point_Structure": {
		"prefix": "Point_Structure",
		"body": [
		  "template < typename T = int > struct Point {",
		  "    T x, y;",
		  "    Point(T _x = 0, T _y = 0) : x(_x), y(_y) {}",
		  "    Point(const Point &p) : x(p.x), y(p.y) {}",
		  "    Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }",
		  "    Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }",
		  "    Point operator * (T c) const { return Point(x * c, y * c); }",
		  "    Point operator / (T c) const { return Point(x / c, y / c); }",
		  "    bool operator == (const Point &p) const { return x == p.x && y == p.y; }",
		  "    bool operator != (const Point &p) const { return x != p.x || y != p.y; }",
		  "    bool operator < (const Point &p) const { return make_pair(y, x) < make_pair(p.y, p.x); }",
		  "    bool operator > (const Point &p) const { return make_pair(y, x) > make_pair(p.y, p.x); }",
		  "    bool operator <= (const Point &p) const { return make_pair(y, x) <= make_pair(p.y, p.x); }",
		  "    bool operator >= (const Point &p) const { return make_pair(y, x) >= make_pair(p.y, p.x); }",
		  "    friend istream& operator >> (istream &in, Point &p) { return in >> p.x >> p.y; }",
		  "    friend ostream& operator << (ostream &out, const Point &p) { return out << p.x << ' ' << p.y; }",
		  "    T dot(const Point &p) const { return x * p.x + y * p.y; }",
		  "    T cross(const Point &p) const { return x * p.y - y * p.x; }",
		  "    T cross(const Point &a, const Point &b) const { return (a - *this).cross(b - *this); }",
		  "    T dist() const { return x * x + y * y; }",
		  "    T dist(const Point &p) const { return (*this - p).dist(); }",
		  "    double distance() const { return sqrt(1.0 * dist()); }",
		  "    double distance(const Point &p) const { return sqrt(1.0 * dist(p)); }",
		  "    double angle() const { return atan2(y, x); }",
		  "    double angle(const Point &p) const { return atan2(cross(p), dot(p)); }",
		  "    Point unit() const { return *this / dist(); }",
		  "    Point perp() const { return Point(-y, x); }",
		  "    Point rotate(double a) const { return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); }",
		  "    Point rotate(const Point &p, double a) const { return (*this - p).rotate(a) + p; }",
		  "    Point normal() const { return perp().unit(); }",
		  "};",
		  ""
		],
		"description": "Point_Structure"
	},
	"Hash_SegmentTree": {
		"prefix": "Hash_SegmentTree",
		"body": [
		  "template < typename T = int , int Base = 0 > struct Hash_SegmentTree {",
		  " ",
		  "    int n, size;",
		  "    vector < T > pow1, pow2, inv1, inv2;",
		  "    const T p1 = 313, p2 = 1013;",
		  "    const T m1 = 1e9 + 7, m2 = 1e9 + 9;",
		  "    vector < Pair < T > > tree;",
		  " ",
		  "    #define LEFT (idx << 1)",
		  "    #define RIGHT ((idx << 1) | 1)",
		  "    ",
		  "    // multiply two numbers and return the result modulo m",
		  "    T mul(T a, T b, T m){",
		  "        return (1LL * a * b) % m;",
		  "    }",
		  " ",
		  "    // add two numbers and return the result modulo m",
		  "    T add(T a, T b, T m){",
		  "        a += b;",
		  "        if(a >= m) a -= m;",
		  "        return a;",
		  "    }",
		  " ",
		  "    // fast modular exponentiation",
		  "    T pow_mod(T b, T e, int m = Mod){",
		  "        T ret = 1;",
		  "        while(e){",
		  "            if(e & 1) ret = mul(ret, b, m);",
		  "            b = mul(b, b, m);",
		  "            e >>= 1;",
		  "        }",
		  "        return ret;",
		  "    }",
		  "    ",
		  "    Hash_SegmentTree(int _n = 0) : n(_n) {",
		  "        size = 1;",
		  "        Pair < T > DEFAULT = {0, 0};",
		  "        while(size < n) size *= 2;",
		  "        tree = vector < Pair < T > > (2 * size, DEFAULT);",
		  "        pow1 = pow2 = inv1 = inv2 = vector < T > (2 * size);",
		  " ",
		  " ",
		  "        pow1[0] = pow2[0] = inv1[0] = inv2[0] = 1;",
		  " ",
		  "        T inv1_val = pow_mod(p1, m1 - 2, m1);",
		  "        T inv2_val = pow_mod(p2, m2 - 2, m2);",
		  " ",
		  "        for(int i = 1; i < 2 * size; i++){",
		  "            pow1[i] = mul(pow1[i - 1], p1, m1);",
		  "            pow2[i] = mul(pow2[i - 1], p2, m2);",
		  "            inv1[i] = mul(inv1[i - 1], inv1_val, m1);",
		  "            inv2[i] = mul(inv2[i - 1], inv2_val, m2);",
		  "        }",
		  "    }",
		  " ",
		  "    // merge two hashes into one",
		  "    Pair < T > merge(const Pair < T >& a, const Pair < T >& b){",
		  "        return {add(a.first, b.first, m1), add(a.second, b.second, m2)};",
		  "    }",
		  " ",
		  "    // build the segment tree",
		  "    void build(const vector < T >& nums, int idx, int lx, int rx){",
		  "        if(Base ? lx >= sz(nums) : lx > sz(nums)) return;",
		  "        if(rx == lx) tree[idx] = {mul(nums[lx - !Base], pow1[idx], m1), mul(nums[lx - !Base], pow2[idx], m2)};",
		  "        else {",
		  "            int mx = (rx + lx) / 2;",
		  "            build(nums, LEFT, lx, mx);",
		  "            build(nums, RIGHT, mx + 1, rx);",
		  "            tree[idx] = merge(tree[LEFT], tree[RIGHT]);",
		  "        }",
		  "    }",
		  " ",
		  "    // build the segment tree from scratch",
		  "    void build(const vector < T >& nums){",
		  "        build(nums, 1, 1, size);",
		  "    }",
		  " ",
		  "    // update the value at index idx to val",
		  "    void update(int index, T val, int idx, int lx, int rx){",
		  "        if(rx == lx) tree[idx] = {mul(val, pow1[idx], m1), mul(val, pow2[idx], m2)};",
		  "        else {  ",
		  "            int mx = (rx + lx) / 2;",
		  "            if(index <= mx) update(index, val, LEFT, lx, mx);",
		  "            else update(index, val, RIGHT, mx + 1, rx);",
		  "            tree[idx] = merge(tree[LEFT], tree[RIGHT]);",
		  "        }",
		  "    }",
		  " ",
		  "    // update the value at index idx to val",
		  "    void update(const int index, const T val){",
		  "        update(index, val, 1, 1, size);",
		  "    }",
		  " ",
		  "    // update the value at index idx to val",
		  "    void update(const int index, char c){",
		  "        update(index, c - 'a' + 1, 1, 1, size);",
		  "    }",
		  " ",
		  "    // get the hash of the range [l, r]",
		  "    Pair < T > query(int l, int r, int idx, int lx, int rx){",
		  "        if(lx > r || l > rx) return {0, 0};",
		  "        if(lx >= l && rx <= r) return tree[idx];",
		  "        int mx = (lx + rx) / 2;",
		  "        return merge(query(l, r, LEFT, lx, mx), query(l, r, RIGHT, mx + 1, rx));",
		  "    }",
		  " ",
		  "    // get the hash of the range [l, r]",
		  "    Pair < T > query(const int l, const int r){",
		  "        auto [h1, h2] = query(l, r, 1, 1, size);",
		  "        return {mul(h1, inv1[l - 1], m1), mul(h2, inv2[l - 1], m2)};",
		  "    }",
		  "};"
		],
		"description": "Hash_SegmentTree"
	},
	"BellmanFord": {
		"prefix": "BellmanFord",
		"body": [
		  "template < typename T = int > struct BellmanFord {",
		  "    ",
		  "    struct Edge {",
		  "        int u, v;",
		  "        T w;",
		  " ",
		  "        Edge(int _u = 0, int _v = 0, T _w = 0) : u(_u), v(_v), w(_w) {}",
		  " ",
		  "        friend istream& operator >> (istream &in, Edge &e) {",
		  "            in >> e.u >> e.v >> e.w;",
		  "            return in;",
		  "        }",
		  " ",
		  "        void inv(){",
		  "            w *= -1;",
		  "        }",
		  "    };",
		  "",
		  "    int n, m, src, dest;",
		  "    vector < Edge > edges;",
		  "    T zero, DEFAULT;",
		  "    vector < T > dist;",
		  "",
		  "    BellmanFord(int _n = 0, int _m = 0, int _src = 1, int _dest = 1){",
		  "        n = _n, m = _m, src = _src, dest = _dest;",
		  "        zero = 0, DEFAULT = numeric_limits < T > :: max() / 2;",
		  "        dist.assign(n + 5, DEFAULT);",
		  "        edges.resize(m);",
		  "    }",
		  "",
		  "    void read_edges(){",
		  "        cin >> edges;",
		  "    }",
		  "",
		  "    void add_edge(int u, int v, T w){",
		  "        edges.emplace_back(u, v, w);",
		  "    }",
		  "",
		  "    void build(){",
		  "        for(int i = 0; i < n; i++)",
		  "            for(auto& [u, v, w] : edges)",
		  "                dist[v] = min(dist[v], min(dist[u], zero) + w);",
		  "    }",
		  "",
		  "    bool has_negative_cycle(){",
		  "        for(auto& [u, v, w] : edges)",
		  "            if(dist[v] > min(dist[u], zero) + w)",
		  "                return true;",
		  "        return false;",
		  "    } ",
		  "",
		  "    T get_dist(int u){",
		  "        return dist[u];",
		  "    }",
		  "",
		  "    T get_min_dist(){",
		  "        return *min_element(dist.begin(), dist.end());",
		  "    }",
		  "};"
		],
		"description": "BellmanFord"
	},
	"Implicit_SplayTree": {
		"prefix": "Implicit_SplayTree",
		"body": [
		  "struct Data {",
		  "    ll val, sum, pref, suff, max_seg;",
		  "    Data() : val(0), sum(0), pref(-LINF), suff(-LINF), max_seg(-LINF) {}",
		  "    Data(ll v) : val(v), sum(val), pref(val), suff(val), max_seg(val) {}",
		  "};",
		  " ",
		  "Data combine(const Data& a, const Data& b){",
		  "    Data res;",
		  "    res.sum = a.sum + b.sum;",
		  "    res.pref = max(a.pref, a.sum + b.pref);",
		  "    res.suff = max(b.suff, b.sum + a.suff);",
		  "    res.max_seg = max({a.max_seg, b.max_seg, a.suff + b.pref});",
		  "    return res;",
		  "}",
		  " ",
		  "template < typename T = int > struct SplayTree { // 0-indexed",
		  "",
		  "    struct Node {",
		  "        ",
		  "        Node *ch[2], *par;",
		  "        T val, update;",
		  "        int subSz;",
		  "        bool is_lazy;",
		  " ",
		  "        Node() : subSz(0), update(0), is_lazy(false) {",
		  "            par = ch[0] = ch[1] = this;",
		  "        }",
		  "        ",
		  "        Node(T V) : val(V), subSz(1), update(0), is_lazy(false) {",
		  "            par = ch[0] = ch[1] = EMPTY;",
		  "        }",
		  "",
		  "        // update node values",
		  "        void update() {",
		  "            subSz = ch[0] -> subSz + ch[1] -> subSz + 1;",
		  "            auto v = val.val;",
		  "            val = combine(ch[0] -> val, combine(Data(v), ch[1] -> val));",
		  "            val.val = v;",
		  "        }",
		  "",
		  "        // push down lazy propagation",
		  "        void push_down(){",
		  "            if(this == EMPTY || !is_lazy) return;",
		  "            val = Data(update * subSz);",
		  "            ch[0] -> lazy_update(update);",
		  "            ch[1] -> lazy_update(update);",
		  "            is_lazy = false;",
		  "        }",
		  "",
		  "        // lazy change",
		  "        void lazy_update(ll c){",
		  "            if(this == EMPTY) return;",
		  "            update = c;",
		  "            is_lazy = true;",
		  "        }",
		  "",
		  "    };",
		  " ",
		  "    static Node* EMPTY;",
		  "    Node *root;",
		  "    enum dir {LEFT, RIGHT};",
		  "    #define returnType ll ",
		  " ",
		  "    SplayTree(){",
		  "        root = EMPTY;",
		  "    }",
		  " ",
		  "    // Link two nodes with direction d",
		  "    void link(Node *p, Node *c, int d){",
		  "        if(p != EMPTY) p -> ch[d] = c, p -> update();",
		  "        if(c != EMPTY) c -> par = p;",
		  "    }",
		  " ",
		  "    // 0 for LEFT, 1 for RIGHT",
		  "    int get_dir(Node *p, Node *c){",
		  "        return p -> ch[RIGHT] == c;",
		  "    }",
		  " ",
		  "    /*",
		  "            gp                       gp",
		  "            | gd                     | gd",
		  "            p                        q",
		  "          / \\d                   !d/  \\",
		  "         a   q    ->         <-   p    c",
		  "          !d/ \\                 / \\d",
		  "           b   c                a   b",
		  "    */",
		  " ",
		  "    // rotate node p with direction d",
		  "    void rotate(Node *p, int d){",
		  "        Node *q = p -> ch[d];",
		  "        Node *gp = p -> par;",
		  "        int gd = get_dir(gp, p);",
		  "        link(p, q -> ch[!d], d);",
		  "        link(q, p, !d);",
		  "        link(gp, q, gd);",
		  "    }",
		  " ",
		  "    // splay node p to the root of the tree it belongs to",
		  "    void splay(Node *q){",
		  "        // splay p until it becomes the root of the tree",
		  "        while(q -> par != EMPTY){",
		  "            Node *p = q -> par;",
		  "            Node *gp = p -> par;",
		  "            int d1 = get_dir(p, q);",
		  "            int d2 = get_dir(gp, p);",
		  "            if(gp == EMPTY){ // direct parent",
		  "                rotate(p, d1);",
		  "            }else if(d1 == d2){ // zig-zig",
		  "                rotate(gp, d2);",
		  "                rotate(p, d1);",
		  "            }else { // zig-zag ",
		  "                rotate(p, d1);",
		  "                rotate(gp, d2);",
		  "            }",
		  "        }",
		  "        root = q;",
		  "    }",
		  " ",
		  "    // split tree into two trees, one with values less than val and the other with values greater than or equal val",
		  "    void split(Node *p, int idx, Node* &ls, Node * &ge){",
		  "        if(idx >= p -> subSz) {",
		  "            ls = p, ge = EMPTY;",
		  "            return;",
		  "        }",
		  "        p = splay_by_idx(p, idx);",
		  "        ls = p -> ch[LEFT];",
		  "        ge = p;",
		  "        link(ge, EMPTY, LEFT);",
		  "        link(EMPTY, ls, RIGHT);",
		  "    }",
		  "",
		  "    // make the node with index idx the root of the tree",
		  "    Node* splay_by_idx(Node* p, int idx){",
		  "        p = at(p, idx);",
		  "        splay(p);",
		  "        return p;",
		  "    }",
		  " ",
		  "    // merge two trees into one tree",
		  "    Node* merge(Node *ls, Node *ge){",
		  "        if(ls == EMPTY) return ge;",
		  "        if(ge == EMPTY) return ls;",
		  "        ge = splay_by_idx(ge, 0);",
		  "        link(ge, ls, LEFT);",
		  "        return ge;",
		  "    }",
		  " ",
		  "    // merge two trees into one tree",
		  "    void merge(Node* p){",
		  "        root = merge(root, p);",
		  "    }",
		  " ",
		  "    // find node with index idx or the node that should be the parent of the node with index idx",
		  "    Node* at(Node *p, int k){",
		  "        if(p == EMPTY) return EMPTY;",
		  "        p -> push_down();",
		  "        if(k > p -> subSz) return EMPTY;",
		  "        int sz = p -> ch[LEFT] -> subSz;",
		  "        if(sz > k) return at(p -> ch[LEFT], k);",
		  "        if(sz + 1 <= k) return at(p -> ch[RIGHT], k - sz - 1);",
		  "        return p;",
		  "    }",
		  "    ",
		  "    // find node with index idx or the node that should be the parent of the node with index idx",
		  "    returnType at(int k){",
		  "        auto p = splay_by_idx(root, k);",
		  "        return p -> val;",
		  "    }",
		  " ",
		  "    // insert node with index idx to the tree",
		  "    void insert(int idx, int val){",
		  "        Node *before, *after;",
		  "        split(root, idx, before, after);",
		  "        Node* between = new Node(val);",
		  "        root = merge(merge(before, between), after);",
		  "    }",
		  "    ",
		  "    // erase node with index idx from the tree",
		  "    void erase(int idx){",
		  "        Node *before, *after, *between;",
		  "        split(root, idx + 1, before, after);",
		  "        split(before, idx, before, between);",
		  "        delete between;",
		  "        root = merge(before, after);",
		  "    }",
		  "    ",
		  "    // replace node with index idx with node with value val",
		  "    void replace(int idx, int val){",
		  "        Node *before, *after, *between;",
		  "        split(root, idx + 1, before, after);",
		  "        split(before, idx, before, between);",
		  "        ",
		  "        // change the value of the node",
		  "        between -> val = val;",
		  "",
		  "        root = merge(merge(before, between), after);",
		  "    }",
		  "",
		  "    //  get query result for the range [s, e]",
		  "    returnType query(int s, int e){",
		  "        Node *before, *after, *between;",
		  "        split(root, e + 1, before, after);",
		  "        split(before, s, before, between);",
		  "        returnType ans = between -> val.max_seg;",
		  "        root = merge(merge(before, between), after);",
		  "        return ans;",
		  "    }",
		  "    ",
		  "    // propagate lazy updates from node q to the root of the tree",
		  "    void push_down_to_root(Node* p){",
		  "        if(p == EMPTY) return;",
		  "        push_down_to_root(p -> par);",
		  "        p -> push_down();",
		  "    }",
		  " ",
		  "    // get the index of node q",
		  "    int get_idx(Node* p){",
		  "        push_down_to_root(p);",
		  "        splay(p);",
		  "        return p -> ch[LEFT] -> subSz;",
		  "    }",
		  " ",
		  "    // get the size of the subtree rooted at node p",
		  "    int get_size(){",
		  "        return root -> subSz;",
		  "    }",
		  " ",
		  "    // print the tree for debugging purposes",
		  "    void print(Node* p, int depth){",
		  "        if(p == EMPTY) return;",
		  "        print(p -> ch[LEFT], depth + 1);",
		  "        cout << string(2 * depth, ' ') << setw(2) << p -> val.val << \"\\n\";",
		  "        print(p -> ch[RIGHT], depth + 1);",
		  "    }",
		  "    ",
		  "    // print the tree for debugging purposes",
		  "    void print(){",
		  "        print(root, 0);",
		  "        cout << \"-----------------------------------\\n\";",
		  "    }",
		  "};",
		  "template < typename T > typename SplayTree < T > :: Node* SplayTree < T > :: EMPTY = new typename SplayTree < T > :: Node();"
		],
		"description": "Implicit_SplayTree"
	},
	"SplayTree": {
		"prefix": "SplayTree",
		"body": [
		  "template < typename T = int > struct SplayTree {",
		  "",
		  "    struct Node {",
		  "        ",
		  "        Node *ch[2], *par;",
		  "        T val;",
		  "        int subSz, freq;",
		  "",
		  "        Node() : subSz(0), freq(0) {",
		  "            par = ch[0] = ch[1] = this;",
		  "            val = numeric_limits < T > :: min();",
		  "        }",
		  "        ",
		  "        Node(T V) : val(V), subSz(1), freq(1) {",
		  "            par = ch[0] = ch[1] = EMPTY;",
		  "        }",
		  "        ",
		  "        void update() {",
		  "            subSz = freq + ch[0] -> subSz + ch[1] -> subSz;",
		  "        }",
		  "    };",
		  "",
		  "    static Node* EMPTY;",
		  "    Node *root;",
		  "    enum dir {LEFT, RIGHT};",
		  "",
		  "    SplayTree(){",
		  "        root = EMPTY;",
		  "    }",
		  "",
		  "    // Link two nodes with direction d",
		  "    void link(Node *p, Node *c, int d){",
		  "        if(p != EMPTY) p -> ch[d] = c, p -> update();",
		  "        if(c != EMPTY) c -> par = p;",
		  "    }",
		  "",
		  "    // 0 for LEFT, 1 for RIGHT",
		  "    int get_dir(Node *p, Node *c){",
		  "        return p -> ch[RIGHT] == c;",
		  "    }",
		  "",
		  "    /*",
		  "            gp                       gp",
		  "            | gd                     | gd",
		  "            p                        q",
		  "          / \\d                   !d/  \\",
		  "         a   q    ->         <-   p    c",
		  "          !d/ \\                 / \\d",
		  "           b   c                a   b",
		  "    */",
		  "",
		  "    // rotate node p with direction d",
		  "    void rotate(Node *p, int d){",
		  "        Node *q = p -> ch[d];",
		  "        Node *gp = p -> par;",
		  "        int gd = get_dir(gp, p);",
		  "        link(p, q -> ch[!d], d);",
		  "        link(q, p, !d);",
		  "        link(gp, q, gd);",
		  "    }",
		  "",
		  "    // splay node p to the root of the tree it belongs to",
		  "    void splay(Node *q){",
		  "        // splay p until it becomes the root of the tree",
		  "        while(q -> par != EMPTY){",
		  "            Node *p = q -> par;",
		  "            Node *gp = p -> par;",
		  "            int d1 = get_dir(p, q);",
		  "            int d2 = get_dir(gp, p);",
		  "            if(gp == EMPTY){ // direct parent",
		  "                rotate(p, d1);",
		  "            }else if(d1 == d2){ // zig-zig",
		  "                rotate(gp, d2);",
		  "                rotate(p, d1);",
		  "            }else { // zig-zag ",
		  "                rotate(p, d1);",
		  "                rotate(gp, d2);",
		  "            }",
		  "        }",
		  "        root = q;",
		  "    }",
		  "",
		  "    // find node with value val or the node that should be the parent of the node with value val",
		  "    Node* find(Node *p, T val){",
		  "        if(p == EMPTY) return EMPTY;",
		  "        Node * ch = p -> ch[val > p -> val];",
		  "        if(p -> val == val || ch == EMPTY) return p;",
		  "        return find(ch, val);",
		  "    }",
		  "",
		  "    // splay node with value val to the root of the tree it belongs to",
		  "    Node* splay_by_value(Node *p, T val){",
		  "        p = find(p, val);",
		  "        splay(p);",
		  "        return p;",
		  "    }",
		  "",
		  "    // insert node with value val to the tree",
		  "    Node* insert(Node *p, T val){",
		  "        if(p == EMPTY) return new Node(val);",
		  "        p = splay_by_value(p, val);",
		  "        if(p -> val == val){",
		  "            p -> freq++;",
		  "            p -> subSz++;",
		  "            return p;",
		  "        }",
		  "        Node *q = new Node(val);",
		  "        if(p -> ch[val > p -> val] != EMPTY){",
		  "            auto ch = p -> ch[val > p -> val];",
		  "            link(p, EMPTY, val > p -> val);",
		  "            link(q, ch, q -> val < ch -> val);",
		  "            link(q, p, q -> val < p -> val);",
		  "            p = q;",
		  "        }else ",
		  "            link(p, q, val > p -> val);",
		  "        return p;",
		  "    }",
		  "",
		  "    // insert node with value val to the tree",
		  "    void insert(T val){",
		  "        root = insert(root, val);",
		  "    }",
		  "",
		  "    // split tree into two trees, one with values less than val and the other with values greater than or equal val",
		  "    void split(Node *p, T val, Node* &ls, Node * &ge){",
		  "        p = splay_by_value(p, val);",
		  "        if(p -> val < val){",
		  "            ls = p;",
		  "            ge = p -> ch[RIGHT];",
		  "            link(ls, EMPTY, RIGHT);",
		  "            link(EMPTY, ge, LEFT);",
		  "        }else {",
		  "            ls = p -> ch[LEFT];",
		  "            ge = p;",
		  "            link(ge, EMPTY, LEFT);",
		  "            link(EMPTY, ls, RIGHT);",
		  "        }",
		  "    }",
		  "",
		  "    // merge two trees into one tree",
		  "    Node* merge(Node *ls, Node *ge){",
		  "        if(ls == EMPTY) return ge;",
		  "        if(ge == EMPTY) return ls;",
		  "        ge = splay_by_value(ge, numeric_limits < T > :: min());",
		  "        link(ge, ls, LEFT);",
		  "        return ge;",
		  "    }",
		  "",
		  "    // erase node with value val from the tree",
		  "    Node* erase(Node *p, T val){",
		  "        p = splay_by_value(p, val);",
		  "        if(p -> val != val) return p;",
		  "        if(p -> freq > 1){",
		  "            p -> freq--;",
		  "            p -> subSz--;",
		  "            return p;",
		  "        } else {",
		  "            Node *ls = p -> ch[LEFT];",
		  "            Node *ge = p -> ch[RIGHT];",
		  "            delete p;",
		  "            link(EMPTY, ls, LEFT);",
		  "            link(EMPTY, ge, RIGHT);",
		  "            return merge(ls, ge);",
		  "        }",
		  "    }",
		  "",
		  "    // erase node with value val from the tree",
		  "    void erase(T val){",
		  "        root = erase(root, val);",
		  "    }",
		  "",
		  "    // find the kth smallest value in the tree",
		  "    Node* kth(Node *p, T k){",
		  "        if(p == EMPTY) return EMPTY;",
		  "        if(k > p -> subSz) return EMPTY;",
		  "        int sz = p -> ch[LEFT] -> subSz;",
		  "        if(sz > k) return kth(p -> ch[LEFT], k);",
		  "        if(sz + p -> freq <= k) return kth(p -> ch[RIGHT], k - sz - p -> freq);",
		  "        return p;",
		  "    }",
		  "",
		  "    // find the kth smallest value in the tree",
		  "    T kth(T k){",
		  "        auto p = kth(root, k);",
		  "        splay(p);",
		  "        root = p;",
		  "        return p -> val;",
		  "    }",
		  "",
		  "    // count the number of values less than val in the tree",
		  "    int count_less(T val){",
		  "        root = splay_by_value(root, val);",
		  "        return root -> ch[LEFT] -> subSz + (root -> val < val ? root -> freq : 0);",
		  "    }",
		  "",
		  "    // get the size of the subtree rooted at node p",
		  "    int get_size(){",
		  "        return root -> subSz;",
		  "    }",
		  "",
		  "    void print(Node* p, int depth){",
		  "        if(p == EMPTY) return;",
		  "        print(p -> ch[LEFT], depth + 1);",
		  "        cout << string(2 * depth, ' ') << setw(2) << p -> val << \"\\n\";",
		  "        print(p -> ch[RIGHT], depth + 1);",
		  "    }",
		  "",
		  "    void print(){",
		  "        print(root, 0);",
		  "        cout << \"-----------------------------------\\n\";",
		  "    }",
		  "",
		  "    bool search(T val){",
		  "        root = splay_by_value(root, val);",
		  "        return root -> val == val;",
		  "    }",
		  "};",
		  "template < typename T > typename SplayTree < T > :: Node* SplayTree < T > :: EMPTY = new typename SplayTree < T > :: Node();",
		  ""
		],
		"description": "SplayTree"
	},
	"SegmentTree2D": {
		"prefix": "SegmentTree2D",
		"body": [
		  "template < typename T = int , int Base = 0 > struct SegmentTree2D {",
		  "",
		  "    struct Node {",
		  "",
		  "        T val;",
		  "",
		  "        Node(T V = 0) : val(V) {}",
		  "    ",
		  "        Node operator = (const T rhs) {",
		  "            val = rhs;",
		  "            return *this;",
		  "        }",
		  "",
		  "    };",
		  "",
		  "    int rows, cols;",
		  "    vector < vector < Node > > tree;",
		  "    Node DEFAULT;",
		  "    #define LEFT(idx) (idx << 1)",
		  "    #define RIGHT(idx) ((idx << 1) | 1)",
		  "    #define VAL val",
		  "    ",
		  "    SegmentTree2D(int n = 0, int m = 0){",
		  "        rows = 1, cols = 1, DEFAULT = 0;",
		  "        while(rows < n) rows *= 2;",
		  "        while(cols < m) cols *= 2;",
		  "        tree = vector < vector < Node > > (2 * rows, vector < Node > (2 * cols, DEFAULT));",
		  "    }",
		  "",
		  "    SegmentTree2D(int n, int m, const vector < vector < T > >& nums){",
		  "        rows = 1, cols = 1, DEFAULT = 0;",
		  "        while(rows < n) rows *= 2;",
		  "        while(cols < m) cols *= 2;",
		  "        tree = vector < vector < Node > > (2 * rows, vector < Node > (2 * cols, DEFAULT));",
		  "        build(nums);",
		  "    }",
		  "",
		  "    // Main operation to do",
		  "    Node operation(const Node& a, const Node& b){",
		  "        return Node(a.val + b.val);",
		  "    }",
		  "",
		  "    // build the current row",
		  "    void build_y(int vx, int lx, int rx, int vy, int ly, int ry, const vector < vector < T > > &vec) {",
		  "        if(Base ? lx >= sz(vec) : lx > sz(vec)) return; // check rows size",
		  "        if(Base ? ly >= sz(vec[0]) : ly > sz(vec[0])) return; // check columns size",
		  "        if (ly == ry) {",
		  "            if (lx == rx) tree[vx][vy] = Node(vec[lx - !Base][ly - !Base]);",
		  "            else tree[vx][vy] = operation(tree[LEFT(vx)][vy], tree[RIGHT(vx)][vy]);",
		  "        } else {",
		  "            int my = (ly + ry) / 2;",
		  "            build_y(vx, lx, rx, LEFT(vy), ly, my, vec);",
		  "            build_y(vx, lx, rx, RIGHT(vy), my + 1, ry, vec);",
		  "            tree[vx][vy] = operation(tree[vx][LEFT(vy)], tree[vx][RIGHT(vy)]);",
		  "        }",
		  "    }",
		  "",
		  "    // build the tree row by row",
		  "    void build_x(int vx, int lx, int rx, const vector < vector < T > > &vec) {",
		  "        if (lx != rx) {",
		  "            int mx = (lx + rx) / 2;",
		  "            build_x(LEFT(vx), lx, mx, vec);",
		  "            build_x(RIGHT(vx), mx + 1, rx, vec);",
		  "        }",
		  "        build_y(vx, lx, rx, 1, 1, cols, vec);",
		  "    }",
		  "    ",
		  "    // build the tree",
		  "    void build(const vector < vector < T > > &vec) {",
		  "        build_x(1, 1, rows, vec);",
		  "    }",
		  "",
		  "    // query the current row",
		  "    Node query_y(int vx, int vy, int tly, int try_, int ly, int ry) {",
		  "        if (ly > ry) return DEFAULT;",
		  "        if (ly == tly && try_ == ry) return tree[vx][vy];",
		  "        int tmy = (tly + try_) / 2;",
		  "        return operation(query_y(vx, LEFT(vy), tly, tmy, ly, min(ry, tmy)), query_y(vx, RIGHT(vy), tmy + 1, try_, max(ly, tmy + 1), ry));",
		  "    }",
		  "",
		  "    // query the tree row by row",
		  "    Node query_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {",
		  "        if (lx > rx) return DEFAULT;",
		  "        if (lx == tlx && trx == rx) return query_y(vx, 1, 1, cols, ly, ry);",
		  "        int tmx = (tlx + trx) / 2;",
		  "        return operation(query_x(LEFT(vx), tlx, tmx, lx, min(rx, tmx), ly, ry), query_x(RIGHT(vx), tmx + 1, trx, max(lx, tmx + 1), rx, ly, ry));",
		  "    }",
		  "",
		  "    // query the tree",
		  "    T query(int lx, int rx, int ly, int ry) {",
		  "        return query_x(1, 1, rows, lx, rx, ly, ry).VAL;",
		  "    }",
		  "",
		  "    // update the current row",
		  "    void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, T val) {",
		  "        if (ly == ry) {",
		  "            if (lx == rx) tree[vx][vy] = Node(val);",
		  "            else tree[vx][vy] = operation(tree[LEFT(vx)][vy], tree[RIGHT(vx)][vy]);",
		  "        } else {",
		  "            int my = (ly + ry) / 2;",
		  "            if (y <= my) update_y(vx, lx, rx, LEFT(vy), ly, my, x, y, val);",
		  "            else update_y(vx, lx, rx, RIGHT(vy), my + 1, ry, x, y, val);",
		  "            tree[vx][vy] = operation(tree[vx][LEFT(vy)], tree[vx][RIGHT(vy)]);",
		  "        }",
		  "    }",
		  "",
		  "    // update the tree row by row",
		  "    void update_x(int vx, int lx, int rx, int x, int y, T val) {",
		  "        if (lx != rx) {",
		  "            int mx = (lx + rx) / 2;",
		  "            if (x <= mx) update_x(LEFT(vx), lx, mx, x, y, val);",
		  "            else update_x(RIGHT(vx), mx + 1, rx, x, y, val);",
		  "        }",
		  "        update_y(vx, lx, rx, 1, 1, cols, x, y, val);",
		  "    }",
		  "",
		  "    // update the tree",
		  "    void update(int x, int y, T val) {",
		  "        update_x(1, 1, rows, x, y, val);",
		  "    }",
		  "",
		  "    // get the value of a cell",
		  "    T get(int x, int y) {",
		  "        return query(x, x, y, y);",
		  "    }",
		  "",
		  "    #undef LEFT",
		  "    #undef RIGHT",
		  "    #undef VAL",
		  "};"
		],
		"description": "SegmentTree2D"
	},
	"KMP": {
		"prefix": "KMP",
		"body": [
		  "struct KMP {",
		  "",
		  "    string pattern;",
		  "    vector < int > lp;",
		  "",
		  "    KMP(const string& str = \"\") : pattern(str) {",
		  "        build();",
		  "    }",
		  "",
		  "    void build(){",
		  "        int n = sz(pattern);",
		  "        lp.resize(n);",
		  "        for(int i = 1; i < n; i++)",
		  "            lp[i] = failure(lp[i - 1], pattern[i]);",
		  "    }",
		  "",
		  "    int failure(int idx, char nxt){",
		  "        while(idx > 0 && pattern[idx] != nxt)",
		  "            idx = lp[idx - 1];",
		  "        return idx + (pattern[idx] == nxt);",
		  "    }",
		  "",
		  "    vector < int > match(const string& str){",
		  "        int n = sz(str), m = sz(pattern);",
		  "        vector < int > ret;",
		  "        for(int i = 0, k = 0; i < n; i++){",
		  "            k = failure(k, str[i]);",
		  "            if(k == m)",
		  "                ret.push_back(i - m + 1); // 0-based indexing",
		  "        }",
		  "",
		  "        for(auto& idx : ret)",
		  "            idx++; // 1-based indexing",
		  "        ",
		  "        return ret;",
		  "    }",
		  "",
		  "    vector < int > count(const string& str){ // count number of occurrences of each prefix",
		  "        int n = sz(str), m = sz(pattern);",
		  "        vector < int > cnt(m + 1);",
		  "        for(int i = 1, k = 0; i < n; i++){",
		  "            k = failure(k, str[i]);",
		  "            cnt[k]++;",
		  "        }",
		  "",
		  "        for(int i = m - 1; i > 0; i--)",
		  "            cnt[lp[i - 1]] += cnt[i]; // number of occurrences of prefix of length lp[i - 1] is at least cnt[i]",
		  " ",
		  "        for(int i = 0; i <= m; i++) ",
		  "            cnt[i]++; // add the whole substring itself",
		  " ",
		  "        return cnt;",
		  "    }",
		  "",
		  "    vector < int > get_prefixes(){",
		  "        vector < int > indexes = {sz(pattern)};",
		  "        for(int i = lp[sz(pattern) - 1]; i > 0; i = lp[i - 1])",
		  "            indexes.push_back(i);",
		  "        sort(all(indexes)); // indexes of prefixes increasing",
		  "        return indexes;",
		  "    }",
		  "};"
		],
		"description": "KMP"
	}
}