snippet for geany

[Default]
ModInt=template <typename T>\nclass Modular {\n public:\n  using Type = typename decay<decltype(T::value)>::type;\n \n  constexpr Modular() : value() {}\n  template <typename U>\n  Modular(const U& x) {\n    value = normalize(x);\n  }\n \n  template <typename U>\n  static Type normalize(const U& x) {\n    Type v;\n    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);\n    else v = static_cast<Type>(x % mod());\n    if (v < 0) v += mod();\n    return v;\n  }\n \n  const Type& operator()() const { return value; }\n  template <typename U>\n  explicit operator U() const { return static_cast<U>(value); }\n  constexpr static Type mod() { return T::value; }\n \n  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }\n  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }\n  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }\n  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }\n  Modular& operator++() { return *this += 1; }\n  Modular& operator--() { return *this -= 1; }\n  Modular operator++(int) { Modular result(*this); *this += 1; return result; }\n  Modular operator--(int) { Modular result(*this); *this -= 1; return result; }\n  Modular operator-() const { return Modular(-value); }\n \n  template <typename U = T>\n  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {\n#ifdef _WIN32\n    uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);\n    uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;\n    asm(\n      "divl %4; \\n\\t"\n      : "=a" (d), "=d" (m)\n      : "d" (xh), "a" (xl), "r" (mod())\n    );\n    value = m;\n#else\n    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));\n#endif\n    return *this;\n  }\n  template <typename U = T>\n  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {\n    int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());\n    value = normalize(value * rhs.value - q * mod());\n    return *this;\n  }\n  template <typename U = T>\n  typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {\n    value = normalize(value * rhs.value);\n    return *this;\n  }\n \n  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }\n \n  template <typename U>\n  friend const Modular<U>& abs(const Modular<U>& v) { return v; }\n \n  template <typename U>\n  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);\n \n  template <typename U>\n  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);\n \n  template <typename U>\n  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);\n \n private:\n  Type value;\n};\n \ntemplate <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }\ntemplate <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }\ntemplate <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }\n \ntemplate <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }\ntemplate <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }\ntemplate <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }\n \ntemplate <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }\n \ntemplate <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }\ntemplate <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }\ntemplate <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }\n \ntemplate <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }\ntemplate <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }\ntemplate <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }\n \ntemplate <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }\ntemplate <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }\ntemplate <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }\n \ntemplate <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }\ntemplate <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }\ntemplate <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }\n \ntemplate<typename T, typename U>\nModular<T> power(const Modular<T>& a, const U& b) {\n  assert(b >= 0);\n  Modular<T> x = a, res = 1;\n  U p = b;\n  while (p > 0) {\n    if (p & 1) res *= x;\n    x *= x;\n    p >>= 1;\n  }\n  return res;\n}\n \ntemplate <typename T>\nbool IsZero(const Modular<T>& number) {\n  return number() == 0;\n}\n \ntemplate <typename T>\nstring to_string(const Modular<T>& number) {\n  return to_string(number());\n}\n \ntemplate <typename T>\nstd::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {\n  return stream << number();\n}\n \ntemplate <typename T>\nstd::istream& operator>>(std::istream& stream, Modular<T>& number) {\n  typename common_type<typename Modular<T>::Type, int64_t>::type x;\n  stream >> x;\n  number.value = Modular<T>::normalize(x);\n  return stream;\n}\n \n/*\nusing ModType = int;\n \nstruct VarMod { static ModType value; };\nModType VarMod::value;\nModType& md = VarMod::value;\nusing Mint = Modular<VarMod>;\n*/\n \nconstexpr int md = 998244353;\nusing Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;\n
Dinic=template <typename T>\nclass flow_graph {\n public:\n  static constexpr T eps = (T) 1e-9;\n \n  struct edge {\n    int from;\n    int to;\n    T c;\n    T f;\n  };\n \n  vector<vector<int>> g;\n  vector<edge> edges;\n  int n;\n  int st;\n  int fin;\n  T flow;\n \n  flow_graph(int _n, int _st, int _fin) : n(_n), st(_st), fin(_fin) {\n    assert(0 <= st && st < n && 0 <= fin && fin < n && st != fin);\n    g.resize(n);\n    flow = 0;\n  }\n \n  void clear_flow() {\n    for (const edge &e : edges) {\n      e.f = 0;\n    }\n    flow = 0;\n  }\n   \n  int add(int from, int to, T forward_cap, T backward_cap) {\n    assert(0 <= from && from < n && 0 <= to && to < n);\n    int id = (int) edges.size();\n    g[from].push_back(id);\n    edges.push_back({from, to, forward_cap, 0});\n    g[to].push_back(id + 1);\n    edges.push_back({to, from, backward_cap, 0});\n    return id;\n  }\n};\n \ntemplate <typename T>\nclass dinic {\n public:\n  flow_graph<T> &g;\n \n  vector<int> ptr;\n  vector<int> d;\n  vector<int> q;\n \n  dinic(flow_graph<T> &_g) : g(_g) {\n    ptr.resize(g.n);\n    d.resize(g.n);\n    q.resize(g.n);\n  }\n \n  bool expath() {\n    fill(d.begin(), d.end(), -1);\n    q[0] = g.fin;\n    d[g.fin] = 0;\n    int beg = 0, end = 1;\n    while (beg < end) {\n      int i = q[beg++];\n      for (int id : g.g[i]) {\n        const auto &e = g.edges[id];\n        const auto &back = g.edges[id ^ 1];\n        if (back.c - back.f > g.eps && d[e.to] == -1) {\n          d[e.to] = d[i] + 1;\n          if (e.to == g.st) {\n            return true;\n          }\n          q[end++] = e.to;\n        }\n      }\n    }\n    return false;\n  }\n   \n  T dfs(int v, T w) {\n    if (v == g.fin) {\n      return w;\n    }\n    int &j = ptr[v];\n    while (j >= 0) {\n      int id = g.g[v][j];\n      const auto &e = g.edges[id];\n      if (e.c - e.f > g.eps && d[e.to] == d[v] - 1) {\n        T t = dfs(e.to, min(e.c - e.f, w));\n        if (t > g.eps) {\n          g.edges[id].f += t;\n          g.edges[id ^ 1].f -= t;\n          return t;\n        }\n      }\n      j--;\n    }\n    return 0;\n  }\n \n  T max_flow() {\n    while (expath()) {\n      for (int i = 0; i < g.n; i++) {\n        ptr[i] = (int) g.g[i].size() - 1;\n      }\n      T big_add = 0;\n      while (true) {\n        T add = dfs(g.st, numeric_limits<T>::max());\n        if (add <= g.eps) {\n          break;\n        }\n        big_add += add;\n      }\n      if (big_add <= g.eps) {\n        break;\n      }\n      g.flow += big_add;\n    }\n    return g.flow;\n  }\n \n  vector<bool> min_cut() {\n    max_flow();\n    vector<bool> ret(g.n);\n    for (int i = 0; i < g.n; i++) {\n      ret[i] = (d[i] != -1);\n    }\n    return ret;\n  }\n};\n
MinCostMaxFlow=template <typename T, typename C>\nclass MinCostMaxFlow {\npublic:\n  static constexpr T eps = (T) 1e-9;\n  struct edge {\n    int from, to;\n    T c, f;\n    C cost;\n  };\nprivate:\n  vector<vector<int>> g;\n  vector<edge> edges;\n  vector<C> d;\n  vector<int> q;\n  vector<bool> in_queue;\n  vector<int> pe;\n  int n, st, fin;\n  T flow;\n  C cost;\npublic:\n  MinCostMaxFlow(int _n, int _st, int _fin) : n(_n), st(_st), fin(_fin) {\n    assert(0 <= st && st < n && 0 <= fin && fin < n && st != fin);\n    g.resize(n);\n    d.resize(n);\n    in_queue.resize(n);\n    pe.resize(n);\n    flow = 0;\n    cost = 0;\n  }\n  void clear_flow() {\n    for (const edge &e : edges) { e.f = 0; }\n    flow = 0;\n  }\n  void add(int from, int to, T forward_cap, T backward_cap, C cost) {\n    assert(0 <= from && from < n && 0 <= to && to < n);\n    g[from].push_back((int) edges.size());\n    edges.push_back({from, to, forward_cap, 0, cost});\n    g[to].push_back((int) edges.size());\n    edges.push_back({to, from, backward_cap, 0, -cost});\n  }\nprivate:\n  bool expath() {\n    fill(d.begin(), d.end(), numeric_limits<C>::max());\n    q.clear();\n    q.push_back(st);\n    d[st] = 0;\n    in_queue[st] = true;\n    int beg = 0;\n    bool found = false;\n    while (beg < (int) q.size()) {\n      int i = q[beg++];\n      if (i == fin) {\n        found = true;\n      }\n      in_queue[i] = false;\n      for (int id : g[i]) {\n        const edge &e = edges[id];\n        if (e.c - e.f > eps && d[i] + e.cost < d[e.to]) {\n          d[e.to] = d[i] + e.cost;\n          pe[e.to] = id;\n          if (!in_queue[e.to]) {\n            q.push_back(e.to);\n            in_queue[e.to] = true;\n          }\n        }\n      }\n    }\n    if (found) {\n      T push = numeric_limits<T>::max();\n      int v = fin;\n      while (v != st) {\n        const edge &e = edges[pe[v]];\n        push = min(push, e.c - e.f);\n        v = e.from;\n      }\n      v = fin;\n      while (v != st) {\n        edge &e = edges[pe[v]];\n        e.f += push;\n        edge &back = edges[pe[v] ^ 1];\n        back.f -= push;\n        v = e.from;\n      }\n      flow += push;\n      cost += push * d[fin];\n    }\n    return found;\n  }\npublic:\n  pair<T, C> GetMinCostMaxFlow() {\n    while (expath()) {}\n    return {flow, cost};\n  }\n};\n

Debug=string to_string(const string& s) { return '"' + s + '"'; }\nstring to_string(const char* s) { return to_string((string) s); }\nstring to_string(bool b) { return (b ? "true" : "false"); }\nstring to_string(vector<bool> v) {\n  string res = "";\n  for (int i = 0, first = 1; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); }\n  return "{" + res + "}";\n}\ntemplate <size_t N>\nstring to_string(bitset<N> v) {\n  string res = "";\n  for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); }\n  return res;\n}\ntemplate <typename A>\nstring to_string(A v) {\n  bool first = false;\n  string res = "{";\n  for (const auto &x : v) {\n    if (first) { res += ", "; }\n    first = true;\n    res += to_string(x);\n  }\n  res += "}";\n  return res;\n}\ntemplate <typename A, typename B>\nstring to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }\ntemplate <typename A, typename B, typename C>\nstring to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; }\nvoid debug_out() { cerr << endl; }\ntemplate <typename Head, typename... Tail>\nvoid debug_out(Head H, Tail... T) {\n  cerr << " " << to_string(H);\n  debug_out(T...);\n}\n#ifndef LOCAL\n  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)\n#else\n  #define debug(...) 0\n#endif\n
Treap=namespace Treap {\n  mt19937 rng;\n  struct treap {\n    treap* l = nullptr;\n    treap* r = nullptr;\n    int key;\n    ll pr;\n    int sz;\n    treap(int ckey) : key(ckey), pr(rng()), sz(1) {}\n  };\n  int gs(treap* v) {\n    return v ? v->sz : 0;\n  }\n  void upd(treap* v) {\n    v->sz = 1 + gs(v->l) + gs(v->r);\n  }\n  treap* merge(treap* l, treap* r) {\n    if (!l || !r) return l ? l : r;\n    if (l->pr > r->pr) {\n      l->r = merge(l->r, r);\n      upd(l);\n      return l;\n    } else {\n      r->l = merge(l, r->l);\n      upd(r);\n      return r;\n    }\n  }\n  pair<treap*, treap*> split(treap* v, int key) {\n    if (!v) return {v, v};\n    if (key >= gs(v->l) + 1) {\n      auto [l, r] = split(v->r, key - 1 - gs(v->l));\n      v->r = l;\n      upd(v);\n      return {v, r};\n    } else {\n      auto [l, r] = split(v->l, key);\n      v->l = r;\n      upd(v);\n      return {l, v};\n    }\n  }\n};\n
SparseTable=template<typename T = int, T def = 0>\nstruct SparseTable {\n    int n, p;\n    vector<vector<T>> t;\n    vector<int> lg2;\n    inline T Func(T& a, T& b) { return (a & b); }\n    SparseTable(const vector<T>& arr)\n        : n(arr.size())\n        , p(log2(n + 1) + 1)\n        , t(p, vector<T>(n, def))\n        , lg2(n + 1, -1)\n    {\n        t[0] = arr;\n        for (int d = 1; d < p; d++) {\n            const int dlt = 1 << (d - 1);\n            for (int i = 0; i + dlt < n; i++) {\n                t[d][i] = Func(t[d - 1][i], t[d - 1][i + dlt]);\n            }\n        }\n        for (int i = 1; i <= n; i++) { lg2[i] = lg2[i >> 1] + 1; }\n    }\n    T operator () (int l, int r) {\n        if (l > r) return def;\n        int d = lg2[r - l + 1];\n        return Func(t[d][l], t[d][r - (1 << d) + 1]);\n    }\n};\n
SegmentTree=template<typename T = int, T def = 0>\nstruct SegmentTree {\n  vector<T> t;\n  SegmentTree(int n) : t(n * 4, def) {}\n  T Func(const T& l, const T& r) { return l + r; }\n  void Update(int v, int tl, int tr, int index, T value) {\n    if (tl + 1 == tr) {\n      t[v] = value;\n    } else {\n      int tm = (tl + tr) / 2;\n      if (index < tm) {\n        Update(v * 2 + 1, tl, tm, index, value);\n      } else {\n        Update(v * 2 + 2, tm, tr, index, value);\n      }\n      t[v] = Func(t[v * 2 + 1], t[v * 2 + 2]);\n    }\n  }\n  T Get(int v, int tl, int tr, int l, int r) {\n    if (tl >= r || tr <= l) return def;\n    if (tl >= l && tr <= r) return t[v];\n    int tm = (tl + tr) / 2;\n    return Func(Get(v * 2 + 1, tl, tm, l, r), Get(v * 2 + 2, tm, tr, l, r));\n  }\n};\n