fork download
copy 
{
	"WrongAwnser": {
	  "prefix": "WrongAwnser",
	  "body": [
		"#include <bits/stdc++.h>",
		"using namespace std;",
		"mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());",
		"",
		"using i16 = short int;",
		"using i32 = int32_t;",
		"using i64 = int64_t;",
		"using ui16 = unsigned short int;",
		"using ui32 = uint32_t;",
		"using ui64 = uint64_t;",
		"",
		"template<class T>",
		"using v = vector<T>;",
		"",
		"#define all(a) (a).begin(), (a).end()",
		"#define open(x) freopen(#x \".inp\", \"r\", stdin), freopen(#x \".out\", \"w\", stdout)",
		"",
		"template<class X, class Y> bool mimi(X &x, const Y &y) {if(x > y) {x = y; return 1;} return 0;}",
		"template<class X, class Y> bool mama(X &x, const Y &y) {if(x < y) {x = y; return 1;} return 0;}",
		"",
		"const i32 N = 2 * 1e5;",
		"const i32 M = 1000000007;",
		"const i32 inf = 1000000009;",
		"const i64 infll = (i64)1000000000000000018;",
		"",
		"void sad(i32 testID) {",
		"	$0",
		"}",
		"",
		"i32 main() {",
		"    auto begin = std::chrono::high_resolution_clock::now();",
		"    ios_base::sync_with_stdio(false);",
		"    cin.tie(NULL); cout.tie(NULL);",
		"",
		"    i32 t = 1;",
		"    cin >> t;",
		"    for(i32 testID = 1; testID <= t; testID++) {",
		"        // cout << \"Case #\" << testID << \":\\n\";",
		"        sad(testID);",
		"    }",
		"    auto end = std::chrono::high_resolution_clock::now();",
		"    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);",
		"    cerr << endl << \"Time measured: \" << elapsed.count() * 1e-9 << \" seconds.\" << endl; ",
		"    return 0;",
		"}",
		""
	  ],
	  "description": "WrongAwnser"
	}
	"Accepted": {
  "prefix": "Accepted",
  "body": [
    "#include <bits/stdc++.h>",
    "using namespace std;",
	"mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());",
    "",
    "#define i32 int",
    "#define i64 long long int",
    "#define ui32 unsigned int",
    "#define ui64 unsigned long long int",
    "",
    "#define all(a) (a).begin(), (a).end()",
    "#define open(x) freopen(#x \".inp\", \"r\", stdin), freopen(#x \".out\", \"w\", stdout)",
    "",
    "const i32 N = 2 * 1e5;",
    "const i32 M = 1000000007;",
    "const i32 inf = 1000000009;",
    "const i64 infll = (i64)1000000000000000018;",
    "",
    "void sad(i32 testID) {",
    "    ",
    "}",
    "",
    "i32 main() {",
	"    auto begin = std::chrono::high_resolution_clock::now();",
    "    ios_base::sync_with_stdio(false);",
    "    cin.tie(NULL); cout.tie(NULL);",
    "",
    "    i32 t = 1;",
    "    cin >> t;",
    "    for(i32 testID = 1; testID <= t; testID++) {",
    "        // cout << \"Case #\" << testID << \":\\n\";",
    "        sad(testID);",
    "    }",
	"    auto end = std::chrono::high_resolution_clock::now();",
	"    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);",
	"    cerr << endl << \"Time measured: \" << elapsed.count() * 1e-9 << \" seconds.\" << endl; ",
    "    return 0;",
    "}",
    ""
  ],
  "description": "Accepted"
}
		  "Power": {
	  "prefix": "Power",
	  "body": [
		"i64 power(i64 base, i64 exp, i64 mod) {",
		"    i64 result = 1;",
		"    for(; exp; exp >>= 1, base = (base * base) % mod) if(exp & 1) result = (result * base) % mod;",
		"    return result;",
		"}"
	  ],
	  "description": "Power"
	}
	
		  "Sieve": {
			"prefix": "Sieve",
			"body": [
			  "vector<i32> p(maxn + 1, 0);",
			  "void Sieve() {",
			  "    for (i32 i = 2; i * i <= maxn; ++i) if (p[i] == 0) for (i32 j = i * i; j <= maxn; j += i) if (p[j] == 0) p[j] = i;",
			  "    for (i32 i = 2; i <= maxn; ++i) if (p[i] == 0)  p[i] = i;",
			  "    return;",
			  "}"
			],
			"description": "Sieve"
		  }
	
		  "primeFactorization": {
			"prefix": "primeFactorization",
			"body": [
			  "vector<i64> factored;",
			  "void factor(i32 n) {",
			  "    factored.clear();",
			  "    while (n != 1) {",
			  "        factored.push_back(v[n]);",
			  "        n /= v[n];",
			  "    }",
			  "}",
			  "",
			  "void sqrfactor(i64 n) {",
			  "    factored.clear();",
			  "    while (n % 2 == 0) {",
			  "        factored.push_back(2);",
			  "        n /= 2;",
			  "    }",
			  "",
			  "    for (i32 i = 3; i * i <= n; i += 2) {",
			  "        while (n % i == 0) {",
			  "            factored.push_back(i);",
			  "            n /= i;",
			  "        }",
			  "    }",
			  "",
			  "    if (n > 1) {",
			  "        factored.push_back(n);",
			  "    }",
			  "}"
			],
			"description": "primeFactorization"
		  }
	
		  "EulerTotient": {
			"prefix": "EulerTotient",
			"body": [
			  "map<i64, i64>  mp;",
			  "i64 res = 1;",
			  "i64 eulerTotient(const i32& n){",
			  "    i64 res = 1;",
			  "    for (i32 it : factored) {",
			  "        if(mp[it] >= 1){",
			  "        	res *= it;",
			  "			mp[it] ++;",
			  "		}",
			  "		else{",
			  "			mp[it] ++;",
			  "			res *= it - 1;",
			  "		}",
			  "    }",
			  "",
			  "    return res;",
			  "}"
			],
			"description": "primeFactorization"
		  }
	
		  "Matrix": {
			"prefix": "Matrix",
			"body": [
			  "class Matrix {",
			  "private:",
			  "    i64 row, col;",
			  "    vector<vector<i64>> data;",
			  "",
			  "pubi64c:",
			  "    Matrix(const vector<vector<i64>>& base) : row(base.size()), col(base[0].size()), data(base) {}",
			  "",
			  "    Matrix(i64 r, i64 c, i64 val) : row(r), col(c), data(vector<vector<i64>>(r, vector<i64>(c, val))) {}",
			  "",
			  "    void fill(const i64& value) {",
			  "        for(auto& row : data)",
			  "            std::fill(row.begin(), row.end(), value);",
			  "    }",
			  "",
			  "    void fix(const i64& current, const i64& value) {",
			  "        for(auto& row : data)",
			  "            for(auto& cell : row)",
			  "                if(cell == current) cell = value;",
			  "    }",
			  "",
			  "    Matrix& operator=(const Matrix& that) {",
			  "        if (this != &that) {",
			  "            row = that.row;",
			  "            col = that.col;",
			  "            data = that.data;",
			  "        }",
			  "        return *this;",
			  "    }",
			  "",
			  "    static i64 multiply(i64 a, i64 b) {",
			  "        if(mod <= 1e9 + 7) return (a * b) % mod;",
			  "        i64 res = 0;",
			  "        a %= mod;",
			  "        while (b > 0) {",
			  "            if (b & 1)",
			  "                res = (res + a) % mod;",
			  "            a = (2 * a) % mod;",
			  "            b >>= 1;",
			  "        }",
			  "        return res;",
			  "    }",
			  "",
			  "    static i64 cal(i64 a, i64 b) {",
			  "        return (a + b % mod) % mod;",
			  "    }",
			  "",
			  "    Matrix operator*(const Matrix& that) const {",
			  "        if (col != that.row) {",
			  "            throw runtime_error(\"segmentation fault\");",
			  "        }",
			  "        Matrix res(row, that.col, 0);",
			  "        for(i32 i = 0; i < row; i++) {",
			  "            for(i32 j = 0; j < that.col; j++) {",
			  "                for(i32 k = 0; k < col; k++) {",
			  "                    res.data[i][j] = cal(res.data[i][j], multiply(data[i][k], that.data[k][j]));",
			  "                }",
			  "            }",
			  "        }",
			  "        return res;",
			  "    }",
			  "",
			  "    Matrix operator^(i64 exp) const {",
			  "        Matrix res(row, col, 0);",
			  "        Matrix base = *this;",
			  "        for(i32 i = 0; i < row; i++) res.data[i][i] = 1; ",
			  "",
			  "        while (exp > 0) {",
			  "            if (exp & 1) res = res * base;",
			  "            base = base * base;",
			  "            exp >>= 1;",
			  "        }",
			  "        return res;",
			  "    }",
			  "",
			  "    Matrix& operator*=(const Matrix& that) {",
			  "        *this = *this * that;",
			  "        return *this;",
			  "    }",
			  "",
			  "    Matrix& operator^=(i64 exp) {",
			  "        *this = *this ^ exp;",
			  "        return *this;",
			  "    }",
			  "",
			  "    bool operator==(const Matrix& that) const {",
			  "        return row == that.row && col == that.col && data == that.data;",
			  "    }",
			  "",
			  "    i64 rows() const { return row; }",
			  "    i64 cols() const { return col; }",
			  "",
			  "    const vector<i64>& operator[](i32 i) const { return data[i]; }",
			  "    vector<i64>& operator[](i32 i) { return data[i]; }",
			  "",
			  "    void print() const {",
			  "        for(const auto& row : data) {",
			  "            for(const auto& cell : row) {",
			  "                cout << cell << \" \";",
			  "            }",
			  "            cout << endl;",
			  "        }",
			  "    }",
			  "};"
			],
			"description": "Matrix"
		  }
	
		  "max_subarray_sum": {
			"prefix": "max_subarray_sum",
			"body": [
			  "vector<i32> res;",
			  "void max_subarray_sum(const vector<i32>& arr) {",
			  "    i32 max_sum = -inf;",
			  "    i32 current_sum = 0;",
			  "    i32 start_index = 0;",
			  "    i32 end_index = 0;",
			  "    i32 temp_start_index = 0;",
			  "",
			  "    for (i32 i = 0; i < arr.size(); ++i) {",
			  "        current_sum += arr[i];",
			  "",
			  "        if (current_sum > max_sum) {",
			  "            max_sum = current_sum;",
			  "            start_index = temp_start_index;",
			  "            end_index = i;",
			  "        }",
			  "",
			  "        if (current_sum < 0) {",
			  "            current_sum = 0;",
			  "            temp_start_index = i + 1;",
			  "        }",
			  "    }",
			  "",
			  "    res = vector<i32>(arr.begin() + start_index, arr.begin() + end_index + 1);",
			  "}"
			],
			"description": "max_subarray_sum"
		  }
	
		  "SegmentTree": {
  "prefix": "SegmentTree",
  "body": [
    "struct STN {i32 val, lazy;};",
    "struct SegmentTree {",
    "    vector<STN> node;",
    "    const STN DEADNODE = {0, 0};",
    "    i32 uu, vv, n;",
    "    SegmentTree(i32 size) : n(size) {",
    "        node.resize(4 * n + 10, DEADNODE);",
    "        this->uu = 0;",
    "        this->vv = n;",
    "    }",
    "    void relength(i32 size){",
    "        n = size;",
    "        node.resize(4 * n + 10, DEADNODE);",
    "        this->uu = 0;",
    "        this->vv = n;",
    "    }",
    "    STN merge(STN a, STN b) {",
    "        return {a.val + b.val, 0};",
    "    }",
    "    void lazy_update(i32 id, i32 l, i32 r){",
    "        if(node[id].lazy != 0){",
    "            node[id << 1].lazy += node[id].lazy;",
    "            node[id << 1 | 1].lazy += node[id].lazy;",
    "            i32 mid = (r + l) >> 1;",
    "            node[id << 1].val += node[id].lazy * (mid - l + 1);",
    "            node[id << 1 | 1].val += node[id].lazy * (r - mid);",
    "            node[id].lazy = 0;",
    "        }",
    "    }",
    "    void updateV(i32 pos, i32 val) {updateV(pos, pos, val, 1, uu, vv);}",
    "    void updateV(i32 u, i32 v, i32 val, i32 id, i32 l, i32 r) {",
    "        if (l > v || r < u) return;",
    "        if (u <= l && r <= v) {",
    "            node[id].val = val;",
    "            return;",
    "        }",
    "        lazy_update(id, l, r);",
    "        i32 mid = (l + r) >> 1;",
    "        updateV(u, v, val, id << 1, l, mid);",
    "        updateV(u, v, val, id << 1 | 1, mid + 1, r);",
    "        node[id] = merge(node[id << 1], node[id << 1 | 1]);",
    "    }",
    "    void update(i32 u, i32 v, i32 val) {update(u, v, val, 1, uu, vv);}",
    "    void update(i32 u, i32 v, i32 val, i32 id, i32 l, i32 r) {",
    "        if (l > v || r < u) return;",
    "        if (u <= l && r <= v) {",
    "            node[id].lazy += val;",
    "            node[id].val += val * (r - l + 1);",
    "            return;",
    "        }",
    "        lazy_update(id, l, r);",
    "        i32 mid = (l + r) >> 1;",
    "        update(u, v, val, id << 1, l, mid);",
    "        update(u, v, val, id << 1 | 1, mid + 1, r);",
    "        node[id] = merge(node[id << 1], node[id << 1 | 1]);",
    "    }",
    "    STN get(i32 u, i32 v) {return get(u, v, 1, uu, vv);}",
    "    STN get(i32 u, i32 v, i32 id, i32 l, i32 r) {",
    "        if (l > v || r < u) return DEADNODE;",
    "        if (u <= l && r <= v) return node[id];",
    "        lazy_update(id, l, r);",
    "        i32 mid = (l + r) >> 1;",
    "        return merge(get(u, v, id << 1, l, mid), get(u, v, id << 1 | 1, mid + 1, r));",
    "    }",
    "};",
    ""
  ],
  "description": "SegmentTree"
}
	
		  "FenwickTree": {
			"prefix": "FenwickTree",
			"body": [
			  "struct FenwickTree {",
			  "    vector<i64> bit1, bit2;",
			  "    i64 n;",
			  "",
			  "    FenwickTree(i64 size) : n(size) {",
			  "        bit1.resize(n + 1, 0);",
			  "        bit2.resize(n + 1, 0);",
			  "    }",
			  "",
			  "    void update(vector<i64>& b, i64 u, i64 v) {",
			  "        i64 idx = u;",
			  "        while (idx <= n) {",
			  "            b[idx] += v;",
			  "            idx += (idx & (-idx));",
			  "        }",
			  "    }",
			  "",
			  "    void update(i64 pos, i64 val){",
			  "        update(pos, pos, val);",
			  "    }",
			  "",
			  "    void update(i64 l, i64 r, i64 val) {",
			  "        update(bit1, l, (n - l + 1) * val);",
			  "        update(bit1, r + 1, -(n - r + 1) * val);",
			  "        update(bit2, l, val);",
			  "        update(bit2, r + 1, -val);",
			  "    }",
			  "",
			  "    i64 getNode(vector<i64>& b, i64 u) {",
			  "        i64 idx = u, ans = 0;",
			  "        while (idx > 0) {",
			  "            ans += b[idx];",
			  "            idx -= (idx & (-idx));",
			  "        }",
			  "        return ans;",
			  "    }",
			  "",
			  "    i64 prefSum(i64 u) {",
			  "        return getNode(bit1, u) - getNode(bit2, u) * (n - u);",
			  "    }",
			  "",
			  "    i64 get(i64 x) {",
			  "        return prefSum(x) - prefSum(x - 1);",
			  "    }",
			  "",
			  "    i64 get(i64 l, i64 r) {",
			  "        return prefSum(r) - prefSum(l - 1);",
			  "    }",
			  "};"
			],
			"description": "FenwickTree"
		  }
	
		  "Dijkstra": {
  "prefix": "Dijkstra",
  "body": [
    "struct Edge {i32 v; i64 c;};",
    "struct Node {i32 idx; i64 val;bool operator<(const Node& other) const {return val > other.val;}};",
    "void dijkstra(i32 n, i32 s, const vector<vector<Edge>>& graph, vector<i64>& dp, vector<i32>& trace) {",
    "    dp.resize(n, infll); dp[s] = 0;",
    "    trace.resize(n, -1);",
    "    priority_queue<Node> pq;",
    "    pq.push({s, 0});",
    "    while (!pq.empty()) {",
    "        Node current = pq.top();",
    "        pq.pop();",
    "        i32 u = current.idx;",
    "        i64 d = current.val;",
    "        if (d > dp[u]) continue;",
    "        for (const Edge& edge : graph[u]) {",
    "            i32 v = edge.v; i64 c = edge.c;",
    "            if (dp[u] + c < dp[v]) {",
    "                dp[v] = dp[u] + c;",
    "                trace[v] = u;",
    "                pq.push({v, dp[v]});",
    "            }",
    "        }",
    "    }",
    "}"
  ],
  "description": "Dijkstra"
}
	
		  "Miller_rabin": {
			"prefix": "Miller_rabin",
			"body": [
			  "bool miller_rabin(i64 n, i64 k) {",
			  "    if (n <= 1) return false;",
			  "    if (n == 2 || n == 3) return true;",
			  "    if (n % 2 == 0) return false;",
			  "",
			  "    i64 r = 0, d = n - 1;",
			  "    while (!(d & 1)) {",
			  "        r++;",
			  "        d /= 2;",
			  "    }",
			  "",
			  "    for(i64 i = 0; i < k; i ++)",
			  "        i64 a = rand() % (n - 4) + 2; ",
			  "        i64 x = power(a, d, n);",
			  "",
			  "        if (x == 1 || x == n - 1) continue;",
			  "",
			  "        for(i64 j = 0; j < r - 1; j ++){",
			  "            x = power(x, 2, n);",
			  "            if (x == n - 1) break;",
			  "        }",
			  "",
			  "        if (x != n - 1) return false; ",
			  "    }",
			  "	",
			  "    return true; ",
			  "}"
			],
			"description": "Miller_rabin"
		  }
	
		  "SparseTable": {
			"prefix": "SparseTable",
			"body": [
			  "struct SparseTableNode{i64 val;};",
			  "struct SparseTable {",
			  "    i64 n;",
			  "    vector<vector<SparseTableNode>> dp;",
			  "    void rebuild(const vector<i32>& a) {",
			  "        n = a.size(); dp.clear();",
			  "        dp.resize(n, vector<SparseTableNode>(__lg(n) + 1));",
			  "        build(a);",
			  "    }",
			  "    SparseTable(const vector<i32>& a) : n(a.size()) {",
			  "        dp.clear();",
			  "        dp.resize(n, vector<SparseTableNode>(__lg(n) + 1));",
			  "        build(a);",
			  "    }",
			  "    SparseTableNode merge(SparseTableNode a, SparseTableNode b) {",
			  "        if(a.val < b.val) return a; return b;",
			  "    }",
			  "    void build(const vector<i32>& a) {",
			  "        for(i32 i = 0; i < n; i ++) dp[i][0] = {a[i]};",
			  "        for(i32 j = 1; j <= __lg(n); j ++)",
			  "            for(i32 i = 0; i < n - (1 << j) + 1; i ++)",
			  "                dp[i][j] = merge(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);",
			  "    }",
			  "    SparseTableNode get(i64 l, i64 r) {",
			  "        i64 minlen = __lg(r - l + 1);",
			  "        return merge(dp[l][minlen], dp[r - (1 << minlen) + 1][minlen]);",
			  "    }",
			  "};"
			],
			"description": "SparseTable"
		  }
	
		  "Trie": {
			"prefix": "Trie",
			"body": [
			  "const i64 max_ = 26;",
			  "struct Trie{",
			  "    struct Node{",
			  "        Node *child[max_];",
			  "        i64 exist, cnt;",
			  "        Node() {for(i32 i = 0; i < max_; i ++) child[i] = NULL; exist = cnt = 0;}",
			  "    };",
			  " ",
			  "    i64 cur; Node *root;",
			  "    Trie() : cur(0) {root = new Node();};",
			  "    void add(string s) {",
			  "        Node *p = root;",
			  "        for (auto f : s) {",
			  "            i64 c = f - 'a';",
			  "            if (p->child[c] == NULL) p->child[c] = new Node();",
			  "            p = p->child[c]; p->cnt++;",
			  "        }",
			  "        p->exist++;",
			  "    }",
			  "",
			  "    bool delete_str(Node *p, string& s, i64 i) {",
			  "        if (i != (i64)s.size()) {",
			  "            i64 c = s[i] - 'a';",
			  "            bool is_deleted = delete_str(p->child[c], s, i + 1);",
			  "            if (is_deleted) p->child[c] = NULL;",
			  "        }",
			  "        else p->exist--;",
			  "        if (p != root) {",
			  "            p->cnt--;",
			  "            if (p->cnt == 0) {delete(p); return true;}",
			  "        }",
			  "        return false;",
			  "    }",
			  "    void erase(string s) {",
			  "        if (find(s) == false) return;",
			  "        delete_str(root, s, 0);",
			  "    }",
			  "    bool find(string s) {",
			  "        Node *p = root;",
			  "        for (auto f : s) {",
			  "            i64 c = f - 'a';",
			  "            if (p->child[c] == NULL) return false;",
			  "            p = p->child[c];",
			  "        }",
			  "        return (p->exist != 0);",
			  "    }",
			  "};"
			],
			"description": "Trie"
		  }
	
		  "LIS": {
			"prefix": "LIS",
			"body": [
			  "void tracei64S(const vector<i32>& a, const vector<i32>& dp, const vector<i32>& b, vector<i32>& trace){",
			  "    i32 res = *max_element(dp.begin(), dp.end()) + 1;",
			  "    for(i32 p = b.size() - 1; p >= 0; p --) if (res == dp[p] + 1) res--, trace.push_back(a[p]);",
			  "    reverse(all(trace));",
			  "}",
			  "i64 LIS(vector<i32>& a, bool with_trace, vector<i32>& trace){",
			  "    i64 n = a.size(); vector<i32> b(n, inf), dp(n, 0);",
			  "    i64 res = 1;",
			  "    for(i32 i = 0; i < n; i ++) {",
			  "        dp[i] = lower_bound(b.begin(), b.begin() + res, a[i]) - b.begin();",
			  "        res = max(res, dp[i] + 1);",
			  "        b[dp[i]] = a[i];",
			  "    }",
			  "    if(with_trace) tracei64S(a, dp, b, trace);",
			  "    return res;",
			  "}"
			],
			"description": "LIS"
		  }
	
		  "LISpair": {
			"prefix": "LISpair",
			"body": [
			  "void tracei64S(const vii& a, const vector<i32>& dp, const vector<i32>& b, vii& trace){",
			  "    i32 res = *max_element(dp.begin(), dp.end()) + 1;",
			  "    for(i32 p = b.size() - 1; p >= 0; p --) if (res == dp[p] + 1) res--, trace.push_back(a[p]);",
			  "    reverse(all(trace));",
			  "}",
			  "",
			  "i64 LIS(vii& a, bool with_trace, vii& trace){",
			  "    i64 n = a.size();",
			  "    vector<i32> b(n, inf), dp(n, 0);",
			  "    sort(all(a));",
			  "    i64 res = 1;",
			  "    for(i32 i = 0; i < n; i ++) {",
			  "        dp[i] = lower_bound(b.begin(), b.begin() + res, a[i].se) - b.begin();",
			  "        res = max(res, dp[i] + 1);",
			  "        b[dp[i]] = a[i].se;",
			  "    }",
			  "    if(with_trace) tracei64S(a, dp, b, trace);",
			  "    return res;",
			  "}"
			],
			"description": "LISpair"
		  }
	
		  "Matrix": {
  "prefix": "Matrix",
  "body": [
    "class Matrix {",
    "private:",
    "    i64 row, col;",
    "    vector<vector<i64>> data;",
    "",
    "public:",
    "    Matrix(const vector<vector<i64>>& base) {",
    "        row = base.size();",
    "        col = base[0].size();",
    "        data = base;",
    "    }",
    "    Matrix(i64 r, i64 c, i64 val) : row(r), col(c), data(vector<vector<i64>>(r, vector<i64>(c, val))) {}",
    "    void fill(const i64& that){for(i32 i = 0; i < data.size(); i ++) for(i32 j = 0; j < data[i].size(); j ++) data[i][j] = that;}",
    "    void fix(const i64& cur, const i64& that){ for(i32 i = 0; i < data.size(); i ++) for(i32 j = 0; j < data[i].size(); j ++) if(data[i][j] == cur) data[i][j] = that;}",
    "    Matrix& operator=(const Matrix& that) {",
    "        if (this != &that) {",
    "            row = that.row;",
    "            col = that.col;",
    "            data = that.data;",
    "        }",
    "        return *this;",
    "    }",
    "    static i64 multiply(i64 a, i64 b){",
    "        if(M <= 1e9 + 7) return (a * b) % M;",
    "        i64 res = 0;",
    "        a %= M;",
    "        while (b > 0) {",
    "            if (b & 1)",
    "                res = (res + a) % M;",
    "            a = (2 * a) % M;",
    "            b >>= 1;",
    "        }",
    "        return res;",
    "    }",
    "",
    "    static i64 cal(i64 a, i64 b){return (a + b) % M;}",
    "    Matrix operator*(const Matrix& that) const {",
    "        if (col != that.row) throw std::runtime_error(\"segmentation fault\");",
    "        Matrix res(row, that.col, 0);",
    "        for(i32 i = 0; i < row; i ++) ",
    "            for(i32 j = 0; j < that.col; j ++) ",
    "                for(i32 k = 0; k < col; k ++) ",
    "                    res.data[i][j] = cal(res.data[i][j], multiply(data[i][k], that.data[k][j]));",
    "        return res;",
    "    }",
    "    Matrix operator^(i64 exp){",
    "        i64 i = row;",
    "        Matrix res(i, i, 0);",
    "        Matrix temp = *this;",
    "        for(i32 j = 0; j < i; j ++) res.data[j][j] = 1;",
    "        while (exp) {",
    "            if (exp & 1) res = res * temp;",
    "            temp = temp * temp;",
    "            exp >>= 1;",
    "        }",
    "        return res;",
    "    }",
    "    Matrix& operator*=(const Matrix& that) {",
    "        if (col != that.row) throw std::runtime_error(\"segmentation fault\");",
    "        Matrix result = (*this) * that;",
    "        (*this) = result;",
    "        return *this;",
    "    }",
    "    Matrix& operator^=(i64 exp) {",
    "        if (exp == 0) {",
    "            Matrix res(row, col, 0);",
    "            for(i32 i = 0; i < row; i ++) res[i][i] = 1;",
    "            (*this) = res;",
    "            return *this;",
    "        }",
    "        Matrix res = *this;",
    "        exp--;",
    "        while (exp > 0) {",
    "            if (exp & 1) (*this) *= res;",
    "            res *= res;",
    "            exp >>= 1;",
    "        }",
    "        return *this;",
    "    }",
    "    bool operator==(const Matrix& that) const {",
    "        if (row != that.row || col != that.col) return false;",
    "        for(i32 i = 0; i < row; i ++) ",
    "            for(i32 j = 0; j < col; j ++) ",
    "                if (data[i][j] != that.data[i][j]) return false;",
    "        return true;",
    "    }",
    "    const vector<i64>& operator[](i32 i) const {return data[i];}",
    "    vector<i64>& operator[](i32 i) {return data[i];}",
    "    void print() const {",
    "        for(i32 i = 0; i < row; i ++){",
    "            for(i32 j = 0; j < col; j ++){",
    "                cout << data[i][j] << \" \";",
    "            }",
    "            cout << endl;",
    "        }",
    "    }",
    "};"
  ],
  "description": "Matrix"
}
	
		  "BerklampMassey": {
			"prefix": "BerklampMassey",
			"body": [
			  "i64 power(i64 base, i64 exp, i64 mod) {",
			  "    i64 temp = base, res = 1;",
			  "    while (exp) {",
			  "        if (exp % 2) res = (res * temp) % mod;",
			  "        temp = (temp * temp) % mod;",
			  "        exp /= 2;",
			  "    }",
			  "    return res;",
			  "}",
			  "",
			  "template<typename T>",
			  "vector<T> berlekampMassey(vector<T> s) {",
			  "    if (s.empty()) return {};",
			  "",
			  "    i32 n = s.size(), L = 0, m = 0; // m = i - f",
			  "    vector<T> C(n), D(n), oldC;",
			  "    C[0] = D[0] = 1;",
			  "    T df1 = 1;  // d(f+1)",
			  "    for (i32 i = 0; i < n; i++) {",
			  "        ++m;",
			  "        // check if C(i) == a(i)",
			  "        // delta = s_i - sum( cj * s(i-j) ) = d(f+1)?",
			  "        T delta = s[i];",
			  "        for (i32 j = 1; j <= L; j++) {",
			  "            delta += C[j] * s[i-j];  // C(j) is already multipi64ed by -1",
			  "            delta %= mod;",
			  "        }",
			  "        if (delta == 0) continue;  // C(i) is correct",
			  "",
			  "        // Update c = c + d",
			  "        oldC = C;",
			  "        T coeff = delta * power(df1, mod - 2, mod) % mod;",
			  "        for (i32 j = m; j < n; j++) {",
			  "            C[j] -= coeff * D[j - m];  // prepend D with m zeroes, multiply by coeff and add to C",
			  "            C[j] = (C[j] + mod * mod) % mod;",
			  "        }",
			  "        if (2*L > i) continue;",
			  "        L = i + 1 - L, D = oldC, df1 = delta, m = 0;",
			  "    }",
			  "    C.resize(L + 1);",
			  "    C.erase(C.begin());",
			  "    for (auto& x : C) x = -x, x = (x + mod * mod) % mod;",
			  "    return C;",
			  "}",
			  "",
			  "// Helper function",
			  "template<typename T>",
			  "vector<T> mul(const vector<T> &a, const vector<T> &b, const vector<T>& c) {",
			  "    vector<T> ret(a.size() + b.size() - 1);",
			  "    // ret = a * b",
			  "    for (i32 i=0; i<(i32)a.size(); i++)",
			  "        for (i32 j=0; j<(i32)b.size(); j++)",
			  "            ret[i+j] += a[i] * b[j], ret[i + j] %= mod;",
			  "",
			  "    i32 n = c.size();",
			  "    // reducing ret mod f(x)",
			  "    for (i32 i=(i32)ret.size()-1; i>=n; i--)",
			  "        for (i32 j=n-1; j>=0; j--)",
			  "            ret[i-j-1] += ret[i] * c[j], ret[i - j - 1] %= mod;",
			  "    ret.resize(min((i32) ret.size(), n));",
			  "    return ret;",
			  "}",
			  "",
			  "// Find k-th element in i64near recurrence: O(d^2 * logn)",
			  "// Need faster code? See https://j...content-available-to-author-only...o.jp/problem/kth_term_of_i64nearly_recurrent_sequence",
			  "//   (but usually not needed since bottleneck is BerlekampMassey",
			  "//",
			  "// Params:",
			  "// - c: as returned by berlekampMassey",
			  "// - s: s0, s1, ..., s(N-1)",
			  "// Returns: s(k)",
			  "template<typename T>",
			  "T check(const vector<T> &c, const vector<T> &s, i64 k) {",
			  "    i32 n = (i32) c.size();",
			  "    assert(c.size() <= s.size());",
			  "",
			  "    vector<T> a = n == 1 ? vector<T>{c[0]} : vector<T>{0, 1}, x{1};",
			  "    for (; k>0; k/=2) {",
			  "        if (k % 2)",
			  "            x = mul(x, a, c);  // mul(a, b) computes a(x) * b(x) mod f(x)",
			  "        a = mul(a, a, c);",
			  "    }",
			  "    x.resize(n);",
			  "",
			  "    T ret = 0;",
			  "    for (i32 i=0; i<n; i++)",
			  "        ret += x[i] * s[i], ret %= mod;",
			  "    return ret;",
			  "}",
			  "",
			  "// Result for f[n]",
			  "template<typename T>",
			  "T main_cal(const vector<T> &f, i64 k) {",
			  "    vector<i64> c = berlekampMassey(f);",
			  "    return check(c, f, k);",
			  "}"
			],
			"description": "BerklampMassey"
		  }
	
		  "dptools": {
  "prefix": "dptools",
  "body": [
    "void add(i32 &a, i32 b) {a = (a + b) % M;}",
    "void gmin(i32 &a, i32 b) {a = min(a, b);}",
    "void gmax(i32 &a, i32 b) {a = max(a, b);}",
    "bool get(i32 mask, i32 idx){return ((mask >> idx) & 1);}",
    "void print(i32 mask, string s) {bitset<3> a(mask); cout << a.to_string() << s;}"
  ],
  "description": "dptools"
}
		  "Tree": {
  "prefix": "Tree",
  "body": [
    "class Tree{",
    "    private:",
    "        vv<vv<i32>> up;",
    "        vv<i32> h;",
    "        i32 n;",
    "    public:",
    "        Tree(i32 size, vv<vv<i32>>& a) : n(size) {",
    "            up = vv<vv<i32>>(__lg(n) + 1, vv<i32>(n, 0));",
    "            h = vv<i32>(n, 0);",
    "            queue<i32> q; q.push(0);",
    "            while (!q.empty()) {",
    "                i32 node = q.front(); q.pop();",
    "                for (auto x : a[node]) {",
    "                    if (x == up[0][node]) continue;",
    "                    up[0][x] = node;",
    "                    h[x] = h[node] + 1;",
    "                    q.push(x);",
    "                }",
    "            }",
    "            for (i16 i = 1; i <= __lg(n); i++)",
    "                for (i32 j = 0; j < n; j++)",
    "                    up[i][j] = up[i - 1][up[i - 1][j]];",
    "        }",
    "        i32 lca(i32 u, i32 v) {",
    "            if (h[u] > h[v]) swap(u, v);",
    "            if (h[u] != h[v]) {",
    "                i32 dif = h[v] - h[u];",
    "                for (i16 i = __lg(dif); i >= 0; i--)",
    "                    if (dif >= (1 << i)) v = up[i][v], dif -= (1 << i);",
    "            }",
    "            if (u == v) return u;",
    "            for (i16 i = __lg(n); i >= 0; i--)",
    "                if (up[i][u] != up[i][v])",
    "                    u = up[i][u], v = up[i][v];",
    "            return up[0][u];",
    "        }",
    "};",
    ""
  ],
  "description": "Tree"
}

"DisjointSets": {
  "prefix": "DisjointSets",
  "body": [
    "struct Save {",
    "    i32 v, rnkv, u, rnku;",
    "    Save() {}",
    "    Save(i32 _v, i32 _rnkv, i32 _u, i32 _rnku)",
    "        : v(_v), rnkv(_rnkv), u(_u), rnku(_rnku) {}",
    "};",
    "struct DisjointSets {",
    "    vector<i32> par, rank;",
    "    i32 comps;",
    "    vector<Save> history;",
    "",
    "    DisjointSets() {}",
    "    DisjointSets(i32 n) {",
    "        par.resize(n); rank.resize(n, 0);",
    "        for (i32 i = 0; i < n; i++) par[i] = i;",
    "        comps = n;",
    "    }",
    "",
    "    i32 root(i32 v) {",
    "        return (v == par[v]) ? v : root(par[v]);",
    "    }",
    "",
    "    bool merge(i32 v, i32 u) {",
    "        v = root(v); u = root(u);",
    "        if (v == u) return false;",
    "        comps--;",
    "        if (rank[v] > rank[u]) swap(v, u);",
    "        history.push_back(Save(v, rank[v], u, rank[u]));",
    "        par[v] = u;",
    "        if (rank[u] == rank[v]) rank[u] ++;",
    "        return true;",
    "    }",
    "",
    "    void rollback() {",
    "        if (history.empty()) return;",
    "        Save x = history.back();",
    "        history.pop_back();",
    "        par[x.v] = x.v; rank[x.v] = x.rnkv;",
    "        par[x.u] = x.u; rank[x.u] = x.rnku;",
    "        comps++;",
    "    }",
    "};"
  ],
  "description": "DisjointSets"
}
"SqrtDecomposition": {
  "prefix": "SqrtDecomposition",
  "body": [
    "vector<vector<i32>> blocks;",
    "vector<vector<i32>> block_freq;",
    "i32 block_size; i32 sq_temp[N];",
    "void sqrt_decomposition(i32 n, i32 k) {",
    "    block_size = sqrt(n);",
    "    blocks.resize((n + block_size - 1) / block_size);",
    "    block_freq.resize(blocks.size(), vector<i32>(k));",
    "    for(i32 i = 0; i < n; i++) {",
    "        blocks[i / block_size].push_back(sq_temp[i]);",
    "        block_freq[i / block_size][sq_temp[i]]++;",
    "    }",
    "}",
    "i32 sqrt_query(i32 q_l, i32 q_r, i32 k) {",
    "    i32 block_l = q_l / block_size;",
    "    i32 block_r = q_r / block_size, cnt = 0;",
    "    if (block_l == block_r) {",
    "        for (i32 i = q_l; i <= q_r; i++) ",
    "            if(sq_temp[i] < k) cnt ++;",
    "    } ",
    "    else {",
    "        for (i32 i = q_l; i < (block_l + 1) * block_size; i++) ",
    "            if(sq_temp[i] < k) cnt++;",
    "        for (i32 i = block_l + 1; i < block_r; i++) ",
    "            for (i32 j = 0; j < k; j++) ",
    "                cnt += block_freq[i][j];",
    "        for (i32 i = block_r * block_size; i <= q_r; i++) ",
    "            if(sq_temp[i] < k) cnt ++;",
    "    }",
    "    return cnt;",
    "}"
  ],
  "description": "SqrtDecomposition"
}

"FenwickTree": {
  "prefix": "FenwickTree",
  "body": [
    "struct FenwickTree {",
    "    vector<i64> node;",
    "    FenwickTree(i32 n) : node(n + 8, 0) {}",
    "    void update(i32 pos, i64 val) {",
    "        for (; pos < node.size(); pos += pos & -pos) ",
    "            node[pos] += val;",
    "    }",
    "    i64 getSum(i32 pos) {",
    "        i64 res = 0;",
    "        for (; pos > 0; pos -= pos & -pos) ",
    "            res += node[pos];",
    "        return res;",
    "    }",
    "    i64 get(i32 l, i32 r) {",
    "        return getSum(r) - getSum(l - 1);",
    "    }",
    "};",
    ""
  ],
  "description": "FenwickTree"
}

"FenwickTree2D": {
  "prefix": "FenwickTree2D",
  "body": [
    "struct FenwickTree2D {",
    "    vector<vector<i64>> node;",
    "    FenwickTree2D(i32 n, i32 m) : node(n + 8, vector<i64>(m + 8, 0)) {}",
    "    void update(i32 x, i32 y, i64 val) {",
    "        for (i32 i = x; i < node.size(); i += i & -i) ",
    "            for (i32 j = y; j < node[0].size(); j += j & -j) ",
    "                node[i][j] += val;",
    "    }",
    "    i64 getSum(i32 x, i32 y) {",
    "        i64 res = 0;",
    "        for (i32 i = x; i > 0; i -= i & -i) ",
    "            for (i32 j = y; j > 0; j -= j & -j) ",
    "                res += node[i][j];",
    "        return res;",
    "    }",
    "    i64 get(i32 x1, i32 y1, i32 x2, i32 y2) {",
    "        return getSum(x2, y2) - getSum(x1 - 1, y2) - getSum(x2, y1 - 1) + getSum(x1 - 1, y1 - 1);",
    "    }",
    "};",
    ""
  ],
  "description": "FenwickTree2D"
}

"FenwickTree3D": {
  "prefix": "FenwickTree3D",
  "body": [
    "struct FenwickTree3D {",
    "    vector<vector<vector<i64>>> node;",
    "    FenwickTree3D(i32 n, i32 m, i32 p) : node(n + 8, vector<vector<i64>>(m + 8, vector<i64>(p + 8, 0))) {}",
    "    ",
    "    void update(i32 x, i32 y, i32 z, i64 val) {",
    "        for (i32 i = x; i < node.size(); i += i & -i) ",
    "            for (i32 j = y; j < node[0].size(); j += j & -j) ",
    "                for (i32 k = z; k < node[0][0].size(); k += k & -k) ",
    "                    node[i][j][k] += val;",
    "    }",
    "",
    "    i64 getSum(i32 x, i32 y, i32 z) {",
    "        i64 res = 0;",
    "        for (i32 i = x; i > 0; i -= i & -i) ",
    "            for (i32 j = y; j > 0; j -= j & -j) ",
    "                for (i32 k = z; k > 0; k -= k & -k) ",
    "                    res += node[i][j][k];",
    "        return res;",
    "    }",
    "    ",
    "    i64 get(i32 x1, i32 y1, i32 z1, i32 x2, i32 y2, i32 z2) {",
    "        return getSum(x2, y2, z2) ",
    "            - getSum(x1 - 1, y2, z2) - getSum(x2, y1 - 1, z2) - getSum(x2, y2, z1 - 1)",
    "            + getSum(x1 - 1, y1 - 1, z2) + getSum(x1 - 1, y2, z1 - 1) + getSum(x2, y1 - 1, z1 - 1)",
    "            - getSum(x1 - 1, y1 - 1, z1 - 1);",
    "    }",
    "};",
    ""
  ],
  "description": "FenwickTree3D"
}

"FastSet": {
  "prefix": "FastSet",
  "body": [
    "struct FastSet {",
    "    static constexpr i32 BASE = 6;",
    "    static constexpr i32 RANGE = 1 << BASE;",
    "    static constexpr i32 FILTER = RANGE - 1;",
    "    i32 N, log;",
    "    vector<vector<i64>> seg;",
    "",
    "    FastSet(i32 _N = 0, bool val = 0) { build(_N, val); }",
    "    ",
    "    void build(i32 _N = 0, bool val = 0) {",
    "        seg.clear(); N = _N, log = 0;",
    "        while(true) {",
    "            seg.emplace_back((_N + FILTER) >> BASE, (val ? ~0ull : 0ull)); ++log;",
    "            if(seg.back().size() <= 1) break;",
    "            _N = seg.back().size();",
    "        }",
    "    }",
    "    ",
    "    void insert(i32 k) {",
    "        i32 id = k >> BASE;",
    "        for(i32 i = 0; i < seg.size(); ++i, k >>= BASE, id >>= BASE) {",
    "            if(seg[i][id] >> (k & FILTER) & 1) break;",
    "            seg[i][id] |= i64(1) << (k & FILTER);",
    "        }",
    "    }",
    "",
    "    void erase(i32 k) {",
    "        if(!(*this)[k]) return;",
    "        i32 id = k >> BASE;",
    "        for(i32 i = 0; i < seg.size(); ++i, k >>= BASE, id >>= BASE) {",
    "            seg[i][id] ^= i64(1) << (k & FILTER);",
    "            if(bool(seg[i][id])) break;",
    "        }",
    "    }",
    "",
    "    bool operator[](i32 k) {",
    "        assert(0 <= k && k < N);",
    "        return seg[0][k >> BASE] >> (k & FILTER) & 1;",
    "    }",
    "",
    "    i32 next(i32 k) {",
    "        i32 id = k >> BASE;",
    "        for(i32 i = 0; i < seg.size(); ++i) {",
    "            if((id = (k >> BASE)) >= seg[i].size()) break;",
    "            i64 x = seg[i][id] >> (k & FILTER);",
    "            if(!x) { k = id + 1; continue; }",
    "            k += __builtin_ctzll(x);",
    "            for(i32 j = i - 1; j >= 0; --j) k = (k << 6) | __builtin_ctzll(seg[j][k]);",
    "            return k;",
    "        }",
    "        return N;",
    "    }",
    "",
    "    i32 prev(i32 k) {",
    "        k = min(k, N - 1);",
    "        i32 id;",
    "        for(i32 i = 0; i < seg.size(); ++i) {",
    "            if(k < 0) break;",
    "            i64 x = seg[i][id = (k >> BASE)] << (FILTER - (k & FILTER));",
    "            if(!x) { k = id - 1; continue; }",
    "            k -= __builtin_clz
	ll(x);",
    "            for(i32 j = i - 1; j >= 0; --j) k = (k << BASE) | (FILTER - __builtin_clzll(seg[j][k]));",
    "            return k;",
    "        }",
    "        return -1;",
    "    }",
    "};"
  ],
  "description": "FastSet"
}
"ConvexHullTrick": {
  "prefix": "ConvexHullTrick",
  "body": [
    "struct Line {",
    "    mutable i64 k, m, p;",
    "    bool operator<(const Line& o) const {return k < o.k;}",
    "    bool operator<(i64 x) const {return p < x;}",
    "};",
    "struct ConvexHullTrick : multiset<Line, less<>> {",
    "    static const i64 INF = LLONG_MAX;",
    "    i64 div(i64 a, i64 b) {",
    "        return a / b - ((a ^ b) < 0 && a % b); ",
    "    }",
    "    bool isect(iterator x, iterator y) {",
    "        if (y == end()) return x->p = INF, 0;",
    "        if (x->k == y->k) x->p = x->m > y->m ? INF : -INF;",
    "        else x->p = div(y->m - x->m, x->k - y->k);",
    "        return x->p >= y->p;",
    "    }",
    "    void push(i64 k, i64 m) {",
    "        auto z = insert({k, m, 0}), y = z ++, x = y;",
    "        while (isect(y, z)) z = erase(z);",
    "        if (x != begin() && isect(-- x, y)) isect(x, y = erase(y));",
    "        while ((y = x) != begin() && (-- x)->p >= y->p)",
    "        isect(x, erase(y));",
    "    }",
    "    i64 get(i64 x) {",
    "        assert(!empty());",
    "        auto l = *lower_bound(x);",
    "        return l.k * x + l.m;",
    "    }",
    "};",
    ""
  ],
  "description": "ConvexHullTrick"
}
"FastSegmentTree": {
  "prefix": "FastSegmentTree",
  "body": [
    "#include <immintrin.h> ",
    "const int _SIZE = 1 << 20, INF = 1e9 + 9;",
    "using T = uint32_t;",
    "T st[2 * _SIZE]; ",
    "const T identity_element = INF;  ",
    "__attribute__((target(\"avx2\"))) __m256i reduce(__m256i a, __m256i b) {",
    "    return _mm256_min_epi32(a, b);",
    "}",
    "T reduce(T a, T b) {",
    "    return min(a, b);",
    "}",
    "void build(int n, const T a[]) {",
    "    for (int i = 0; i < n; i++) st[i + _SIZE] = a[i + 1];",
    "    for (int i = _SIZE - 1; i > 0; i--) {",
    "        st[i] = reduce(st[i << 1], st[i << 1 | 1]);",
    "    }",
    "}",
    "__attribute__((target(\"avx2\"))) T query_parallel(int l, int r) {",
    "    T res = identity_element;",
    "    l += _SIZE, r += _SIZE;",
    "    __m256i vec_res = _mm256_set1_epi32(res);  ",
    "",
    "    while (l <= r) {",
    "        if (l & 1) {",
    "            __m256i vec_l = _mm256_set1_epi32(st[l]);",
    "            vec_res = reduce(vec_res, vec_l); ",
    "            ++l;",
    "        }",
    "        if (!(r & 1)) {",
    "            __m256i vec_r = _mm256_set1_epi32(st[r]);",
    "            vec_res = reduce(vec_res, vec_r);  ",
    "            --r;",
    "        }",
    "        l >>= 1, r >>= 1;",
    "    }",
    "",
    "    T result[8];",
    "    _mm256_storeu_si256((__m256i*)result, vec_res);",
    "    for (int i = 0; i < 8; i++) {",
    "        res = reduce(res, result[i]);",
    "    }",
    "    return res;",
    "}",
    "void upd(int p, T val) {",
    "    for (st[p += _SIZE] = val; p > 1; p >>= 1) {",
    "        st[p >> 1] = reduce(st[p], st[p ^ 1]);",
    "    }",
    "}",
    "void update(int pos, int val) {upd(pos - 1, val);}",
    "T get(int l, int r) {return query_parallel(l - 1, r - 1);}"
  ],
  "description": "FastSegmentTree"
},

"Checker": {
  "prefix": "Checker",
  "body": [
    "#include <bits/stdc++.h>",
    "using namespace std;",
    "",
    "using i32 = int32_t;",
    "using i64 = int64_t;",
    "",
    "template<class T>",
    "using v = vector<T>;",
    "",
    "#define all(a) (a).begin(), (a).end()",
    "",
    "string file = \"DRAWATREE\";",
    "",
    "i64 rand(i64 l, i64 h) {",
    "    return l + (rand() % (h - l + 1));",
    "}",
    "",
    "void check() {",
    "    ofstream out(file + \".inp\");",
    "",
    "    i32 n = 600; out << n << endl;",
    "    for (i32 i = 0; i < n - 1; i++) {",
    "        for (i32 j = i + 1; j < n; j++) {",
    "            out << (rand(0, 2) == 0? 'N' : 'Y');",
    "        }",
    "        out << endl;",
    "    }",
    "",
    "    out.close();",
    "}",
    "",
    "void sad(i32 testID) {",
    "    srand(time(NULL));",
    "    for (i32 i = 1; i <= 100; i++) { ",
    "        check();",
    "        system((file + \".exe\").c_str());      ",
    "        system((file + \"_trau.exe\").c_str());  ",
    "        if (system((\"fc \" + (file + \".out\") + \" \" + (file + \".ans\")).c_str())) {",
    "            // cout << \"Test \" << i << \" failed!\\n\";",
    "            return;",
    "        }",
    "    }",
    "}",
    "",
    "i32 main() {",
    "    ios_base::sync_with_stdio(false);",
    "    cin.tie(NULL); cout.tie(NULL);",
    "",
    "    i32 t = 1;",
    "    for (i32 testID = 1; testID <= t; testID++) {",
    "        sad(testID);",
    "    }",
    "    return 0;",
    "}",
    ""
  ],
  "description": "Checker"
},
"mul": {
  "prefix": "mul",
  "body": [
    "ui64 modmul(ui64 a, ui64 b, ui64 M){",
    "    i64 ret = a * b - M * ui64(1.L / M * a * b);",
    "    return ret + M * (ret < 0) - M * (ret >= (i64)M);",
    "}"
  ],
  "description": "mul"
}
"PollardRho": {
  "prefix": "PollardRho",
  "body": [
    "ui64 PollardRho(ui64 n){",
    "    auto f = [n](ui64 x){return modmul(x, x, n) + 1;};",
    "    ui64 x=0, y=0, t=30, prd=2, i=1, q;",
    "    while (t++ % 40 || __gcd(prd, n) == 1){",
    "        if (x == y) x = ++i, y = f(x);",
    "        if ((q = modmul(prd, max(x, y) - min(x, y), n))) prd = q;",
    "        x = f(x), y = f(f(y));",
    "    }",
    "    return __gcd(prd, n);",
    "}",
    "vector<ui64> factor(ui64 n){",
    "    if (n == 1) return{};",
    "}"
  ],
  "description": "PollardRho"
}
"BetterSieve": {
  "prefix": "BetterSieve",
  "body": [
    "vector<i32> _checkPrime(N >> 6), _prime;",
    "void Sieve() {",
    "    #define set(n) (_checkPrime[n >> 6] |= (1<<((n & 63) >> 1)))",
    "    #define get(n) (_checkPrime[n >> 6] & (1 << ((n & 63) >> 1)))",
    "    ",
    "    _prime.push_back(2); i32 t = sqrt(N);",
    "    for (i32 i = 3; i < N; i += 2)",
    "        if (!get(i)) {",
    "            _prime.push_back(i);",
    "            if (i > t) continue;",
    "            for (i32 j = i * i; j < N; j += (i << 1)) set(j);",
    "        }",
    "}"
  ],
  "description": "BetterSieve"
}
"gcd_withExtendedEuclidean": {
  "prefix": "gcd_withExtendedEuclidean",
  "body": [
    "i64 gcd_withExtendedEuclidean(i64 a, i64 b, i64 &x, i64 &y) {",
    "    if (b == 0) {x = 1, y = 0; return a;}",
    "    i64 x1, y1, g = gcd_withExtendedEuclidean(b, a % b, x1, y1);",
    "    x = y1; y = x1 - a / b * y1;",
    "    return g;",
    "}"
  ],
  "description": "gcd_withExtendedEuclidean"
}
"custom_hash ": {
  "prefix": "custom_hash ",
  "body": [
    "// Source: http://x...content-available-to-author-only...i.it/splitmix64.c",
    "struct custom_hash {",
    "    static uint64_t splitmix64(uint64_t x) {",
    "        x += 0x9e3779b97f4a7c15;",
    "        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;",
    "        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;",
    "        return x ^ (x >> 31);",
    "    }",
    "    size_t operator()(uint64_t x) const {",
    "        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();",
    "        return splitmix64(x + FIXED_RANDOM);",
    "    }",
    "};"
  ],
  "description": "custom_hash "
}
"MergeSortTree ": {
  "prefix": "MergeSortTree ",
  "body": [
    "struct MSTN {vector<i32> val;};",
    "struct MergeSortTree {",
    "    vector<MSTN> node;",
    "    i32 uu, vv, n;",
    "    MergeSortTree(i32 size) : n(size) {",
    "        node.resize(4 * n + 10);",
    "        this->uu = 1;",
    "        this->vv = n;",
    "    }",
    "    void relength(i32 size){",
    "        n = size;",
    "        node.resize(4 * n + 10);",
    "        this->uu = 1;",
    "        this->vv = n;",
    "    }",
    "    void merge(MSTN &a, MSTN &b, MSTN &c) {",
    "        a.val.clear();",
    "        i32 p1 = 0, p2 = 0;",
    "        while(true) {",
    "            if(p1 == b.val.size()) {",
    "                if(p2 == c.val.size()) break;",
    "                else a.val.push_back(c.val[p2 ++]);",
    "            }",
    "            else {",
    "                if(p2 == c.val.size()) a.val.push_back(b.val[p1 ++]);",
    "                else if(b.val[p1] < c.val[p2]) a.val.push_back(b.val[p1 ++]);",
    "                else a.val.push_back(c.val[p2 ++]);",
    "            }",
    "        }",
    "    }",
    "    void build(vector<i32> &a) {build(1, 1, n, a);}",
    "    void build(i32 id, i32 l, i32 r, vector<i32> &a) {",
    "        if (l == r) {",
    "            node[id].val.push_back(a[l]);",
    "            return;",
    "        }",
    "        i32 mid = (l + r) >> 1;",
    "        build(id << 1, l, mid, a);",
    "        build(id << 1 | 1, mid + 1, r, a);",
    "        merge(node[id], node[id << 1], node[id << 1 | 1]);",
    "    }",
    "    void updateV(i32 pos, i32 x, i32 y) {updateV(pos, x, y, 1, uu, vv);}",
    "    void updateV(i32 pos, i32 x, i32 y, i32 id, i32 l, i32 r) {",
    "        if (l > pos || r < pos) return;",
    "        if (l == r) {",
    "            i32 ll = 0, rr = node[id].val.size() - 1, res = 0;",
    "            while(ll <= rr) {",
    "                i32 mid = (ll + rr) >> 1;",
    "                if(node[id].val[mid] >= x) rr = (res = mid) - 1;",
    "                else ll = mid + 1;",
    "            }",
    "            if(node[id].val[res] == x) node[id].val[res] = y;",
    "            else throw std::runtime_error(\"Value not found\");",
    "            sort(all(node[id].val));",
    "            return;",
    "        }",
    "        i32 mid = (l + r) >> 1;",
    "        updateV(pos, x, y, id << 1, l, mid);",
    "        updateV(pos, x, y, id << 1 | 1, mid + 1, r);",
    "        merge(node[id], node[id << 1], node[id << 1 | 1]);",
    "    }",
    "    i32 get(i32 u, i32 v, i32 k) {return get(u, v, k, 1, uu, vv);}",
    "    i32 get(i32 u, i32 v, i32 k, i32 id, i32 l, i32 r) {",
    "        if (l > v || r < u) return 0;",
    "        if (u <= l && r <= v) {",
    "            i32 ll = 0, rr = node[id].val.size() - 1, res = node[id].val.size();",
    "            while(ll <= rr) {",
    "                i32 mid = (ll + rr) >> 1;",
    "                if(node[id].val[mid] > k) rr = (res = mid) - 1;",
    "                else ll = mid + 1;",
    "            }",
    "            return node[id].val.size() - res;",
    "        }",
    "        i32 mid = (l + r) >> 1;",
    "        return get(u, v, k, id << 1, l, mid) + get(u, v, k, id << 1 | 1, mid + 1, r);",
    "    }",
    "};"
  ],
  "description": "MergeSortTree "
}
"DynamicConnectivity": {
  "prefix": "DynamicConnectivity",
  "body": [
    "struct Connect {",
    "    i32 v, u;",
    "    bool united;",
    "    Connect(i32 _v, i32 _u) : v(_v), u(_u) {",
    "    }",
    "};",
    "struct DynamicConnectivity {",
    "    vector<vector<Connect>> t;",
    "    DisjointSets dsu;",
    "    i32 T;",
    "",
    "    DynamicConnectivity() {}",
    "    DynamicConnectivity(i32 _T, i32 n) : T(_T) {",
    "        dsu = DisjointSets(n);",
    "        t.resize(4 * T + 4);",
    "    }",
    "",
    "    void add(i32 v, i32 l, i32 r, i32 ul, i32 ur, Connect& q) {",
    "        if (ul > ur)",
    "            return;",
    "        if (l == ul && r == ur) {",
    "            t[v].push_back(q);",
    "            return;",
    "        }",
    "        i32 mid = (l + r) >> 1;",
    "        add(v << 1, l, mid, ul, min(ur, mid), q);",
    "        add(v << 1 | 1, mid + 1, r, max(ul, mid + 1), ur, q);",
    "    }",
    "    void add(Connect q, i32 l, i32 r) {",
    "        add(1, 0, T - 1, l, r, q);",
    "    }",
    "",
    "    void dfs(i32 v, i32 l, i32 r, vector<i32>& ans) {",
    "        for (Connect& q : t[v]) {",
    "            q.united = dsu.merge(q.v, q.u);",
    "        }",
    "        if (l == r) ans[l] = dsu.comps;",
    "        else {",
    "            i32 mid = (l + r) >> 1;",
    "            dfs(v << 1, l, mid, ans);",
    "            dfs(v << 1 | 1, mid + 1, r, ans);",
    "        }",
    "        for (Connect q : t[v]) if (q.united) dsu.rollback();",
    "    }",
    "    vector<i32> compute() {",
    "        vector<i32> ans(T);",
    "        dfs(1, 0, T - 1, ans);",
    "        return ans;",
    "    }",
    "};"
  ],
  "description": "DynamicConnectivity"
}
	}
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: class, interface, or enum expected
{
^
Main.java:1153: error: unclosed string literal
    "            k -= __builtin_clz
    ^
Main.java:1154: error: unclosed string literal
	ll(x);",
	      ^
Main.java:1155: error: class, interface, or enum expected
    "            for(i32 j = i - 1; j >= 0; --j) k = (k << BASE) | (FILTER - __builtin_clzll(seg[j][k]));",
                                                                                                          ^
4 errors
stdout
copy 
Standard output is empty
https://ideone.com/7IG641
language:
Java (HotSpot 12)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!