text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/cycles/DirectedCycle.h"
#include "../../../../Content/C++/graph/representations/StaticGraph.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int V = 2e6, E = 4e6;
  StaticGraph G(V);
  G.reserveDiEdges(E);
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    G.addDiEdge(v, w);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  DirectedCycle cycle(G);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v : cycle.cycle) checkSum = 31 * checkSum + v;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  mt19937_64 rng(0);
  int V = 4e6, E = 4e6;
  StaticGraph G(V);
  G.reserveDiEdges(E);
  for (int i = 0; i < E; i++) {
    int v = i, w = (i + 1) % V;
    G.addDiEdge(v, w);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  DirectedCycle cycle(G);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v : cycle.cycle) checkSum = 31 * checkSum + v;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/cycles/FourCycles.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e4;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int V = rng() % 9, E = rng() % (V * (V - 1) / 2 + 1);
    vector<pair<int, int>> edges;
    set<pair<int, int>> S;
    vector<long long> X(V), Y(E);
    for (auto &&x : X) x = rng() % int(1e6) + 1;
    for (int i = 0; i < E; i++) {
      int a, b;
      do {
        a = rng() % V;
        b = rng() % V;
      } while (a == b || S.count(make_pair(a, b)) || S.count(make_pair(b, a)));
      S.emplace(a, b);
      edges.emplace_back(a, b);
      Y[i] = rng() % (int(1e6)) + 1;
    }
    long long cnt0 = 0;
    for (int i = 0; i < E; i++) {
      for (int j = 0; j < i; j++) {
        for (int k = 0; k < j; k++) {
          for (int m = 0; m < k; m++) {
            unordered_map<int, int> umap;
            umap[edges[i].first]++;
            umap[edges[i].second]++;
            umap[edges[j].first]++;
            umap[edges[j].second]++;
            umap[edges[k].first]++;
            umap[edges[k].second]++;
            umap[edges[m].first]++;
            umap[edges[m].second]++;
            int cntTwo = 0;
            for (auto &&p : umap) cntTwo += p.second == 2;
            cnt0 += cntTwo == 4;
          }
        }
      }
    }
    long long cnt1 = fourCycles(V, edges);
    assert(cnt0 == cnt1);
    checkSum = 31 * cnt0;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}

repo_name: wesley-a-leung/Resources

mime_type: text/x-c++


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/cycles/FourCycles.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int V = 2e5, E = 1e6;
  vector<pair<int, int>> edges;
  set<pair<int, int>> S;
  vector<long long> X(V), Y(E);
  for (auto &&x : X) x = rng() % int(1e6) + 1;
  for (int i = 0; i < E; i++) {
    int a, b;
    do {
      a = rng() % V;
      b = rng() % V;
    } while (a == b || S.count(make_pair(a, b)) || S.count(make_pair(b, a)));
    S.emplace(a, b);
    edges.emplace_back(a, b);
    Y[i] = rng() % (int(1e6)) + 1;
  }
  const auto start_time = chrono::system_clock::now();
  long long checkSum = fourCycles(V, edges);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Random) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  mt19937_64 rng(0);
  int V = 2e5, E = 1e6;
  vector<pair<int, int>> edges;
  set<pair<int, int>> S;
  vector<long long> X(V), Y(E);
  for (auto &&x : X) x = rng() % int(1e6) + 1;
  int sqrtE = sqrt(E);
  for (int i = 0; i < E; i++) {
    int a, b;
    do {
      if (i < sqrtE * (sqrtE - 1) / 2) {
        a = rng() % sqrtE;
        b = rng() % sqrtE;
      } else {
        a = rng() % V;
        b = rng() % V;
      }
    } while (a == b || S.count(make_pair(a, b)) || S.count(make_pair(b, a)));
    S.emplace(a, b);
    edges.emplace_back(a, b);
    Y[i] = rng() % (int(1e6)) + 1;
  }
  const auto start_time = chrono::system_clock::now();
  long long checkSum = fourCycles(V, edges);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Small Dense Cluster) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/cycles/EulerianWalk.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int V = 2e5, E = 1e6;
  vector<pair<int, int>> edges;
  edges.reserve(E);
  edges.emplace_back(rng() % V, rng() % V);
  for (int i = 1; i < E - 1; i++) edges.emplace_back(edges.back().second, rng() % V);
  edges.emplace_back(edges.back().second, edges[0].first);
  const auto start_time = chrono::system_clock::now();
  vector<int> walk = eulerianWalk(V, edges, true, true);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v : walk) checkSum = 31 * checkSum + v;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/cycles/Triangles.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e4;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int V = rng() % 9, E = rng() % (V * (V - 1) / 2 + 1);
    vector<pair<int, int>> edges;
    set<pair<int, int>> S;
    vector<long long> X(V), Y(E);
    for (auto &&x : X) x = rng() % int(1e6) + 1;
    for (int i = 0; i < E; i++) {
      int a, b;
      do {
        a = rng() % V;
        b = rng() % V;
      } while (a == b || S.count(make_pair(a, b)) || S.count(make_pair(b, a)));
      S.emplace(a, b);
      edges.emplace_back(a, b);
      Y[i] = rng() % (int(1e6)) + 1;
    }
    long long cnt0 = 0, vertSum0 = 0, edgeSum0 = 0, cnt1 = 0, vertSum1 = 0, edgeSum1 = 0;
    for (int i = 0; i < E; i++) {
      for (int j = 0; j < i; j++) {
        for (int k = 0; k < j; k++) {
          unordered_set<int> uset;
          uset.insert(edges[i].first);
          uset.insert(edges[i].second);
          uset.insert(edges[j].first);
          uset.insert(edges[j].second);
          uset.insert(edges[k].first);
          uset.insert(edges[k].second);
          if (int(uset.size()) == 3) {
            cnt0++;
            long long prod = 1;
            for (int a : uset) prod *= X[a];
            vertSum0 += prod;
            edgeSum0 += Y[i] * Y[j] * Y[k];
          }
        }
      }
    }
    triangles(V, edges, [&] (int a, int b, int c, int i, int j, int k) {
      cnt1++;
      vertSum1 += X[a] * X[b] * X[c];
      edgeSum1 += Y[i] * Y[j] * Y[k];
    });
    assert(cnt0 == cnt1);
    assert(vertSum0 == vertSum1);
    assert(edgeSum0 == edgeSum1);
    checkSum = 31 * checkSum + vertSum0;
    checkSum = 31 * checkSum + edgeSum0;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/queries/WaveletMatrixTreeAggregation.h"
#include "../../../../Content/C++/graph/queries/WaveletMatrixHeavyLightDecomposition.h"
#include "../../../../Content/C++/graph/representations/StaticGraph.h"
#include "../../../../Content/C++/datastructures/trees/fenwicktrees/BitFenwickTree.h"
using namespace std;

struct R1 {
  using Data = int;
  using Lazy = int;
  static Data qdef() { return 0; }
  static Data merge(const Data &l, const Data &r) { return l + r; }
  static Data invData(const Data &v) { return -v; }
  BitFenwickTree FT;
  R1(const vector<Data> &A) : FT(A.size()) {
    for (int i = 0; i < int(A.size()); i++) FT.set(i, A[i]);
    FT.build();
  }
  void update(int i, const Lazy &val) { FT.update(i, val); }
  Data query(int r) { return FT.query(r); }
};

struct R2 {
  using Data = int;
  using Lazy = int;
  static Data qdef() { return 0; }
  static Data merge(const Data &l, const Data &r) { return l + r; }
  BitFenwickTree FT;
  R2(const vector<Data> &A) : FT(A.size()) {
    for (int i = 0; i < int(A.size()); i++) FT.set(i, A[i]);
    FT.build();
  }
  void update(int i, const Lazy &val) { FT.update(i, val); }
  Data query(int l, int r) { return FT.query(l, r); }
};

void test1() {
  mt19937_64 rng(0);
  constexpr const int V = 2e5, Q = 2e5, MAXA = 1e9;
  vector<int> A(V, 0);
  for (int v = 0; v < V; v++) A[v] = rng() % MAXA;
  vector<int> X(V, 0);
  for (int v = 0; v < V; v++) X[v] = rng() % 2;
  StaticGraph G(V);
  for (int v = 1; v < V; v++) G.addBiEdge(rng() % v, v);
  G.build();
  const auto start_time = chrono::system_clock::now();
  WaveletMatrixTreeAggregation<int, R1, false> wm(G, A, X);
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int t = rng() % 3;
    if (t == 0) {
      int v = rng() % V;
      wm.update(v, X[v] ^= 1);
    } else if (t == 1) {
      int v = rng() % V, w = rng() % V;
      int a = rng() % MAXA, b = rng() % MAXA;
      if (a > b) swap(a, b);
      ans.push_back(wm.query(v, w, a, b));
    } else {
      int v = rng() % V, w = rng() % V;
      int k = rng() % ((wm.query(v, v, MAXA) + 1) * 2);
      vector<int> C;
      sort(C.begin(), C.end());
      pair<bool, int *> p = wm.bsearch(v, w, [&] (int agg) {
        return agg >= k;
      });
      ans.push_back(p.first ? *p.second : INT_MAX);
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Euler Tour) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  V: " << V << endl;
  cout << "  Q: " << Q << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  mt19937_64 rng(0);
  constexpr const int V = 2e5, Q = 2e5, MAXA = 1e9;
  vector<int> A(V, 0);
  for (int v = 0; v < V; v++) A[v] = rng() % MAXA;
  vector<int> X(V, 0);
  for (int v = 0; v < V; v++) X[v] = rng() % 2;
  StaticGraph G(V);
  for (int v = 1; v < V; v++) G.addBiEdge(rng() % v, v);
  G.build();
  const auto start_time = chrono::system_clock::now();
  WaveletMatrixHLD<int, R2, false> wm(G, A, X);
  vector<int> ans;
  ans.reserve(Q);
  for (int i = 0; i < Q; i++) {
    int t = rng() % 3;
    if (t == 0) {
      int v = rng() % V;
      wm.update(v, X[v] ^= 1);
    } else if (t == 1) {
      int v = rng() % V, w = rng() % V;
      int a = rng() % MAXA, b = rng() % MAXA;
      if (a > b) swap(a, b);
      ans.push_back(wm.query(v, w, a, b));
    } else {
      int v = rng() % V, w = rng() % V;
      int k = rng() % ((wm.query(v, v, MAXA) + 1) * 2);
      vector<int> C;
      sort(C.begin(), C.end());
      pair<bool, int *> p = wm.bsearch(v, w, [&] (int agg) {
        return agg >= k;
      });
      ans.push_back(p.first ? *p.second : INT_MAX);
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (HLD) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  V: " << V << endl;
  cout << "  Q: " << Q << endl;
  long long checkSum = 0;
  for (auto &&a : ans) checkSum = 31 * checkSum + a;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/queries/WaveletMatrixTreeAggregation.h"
#include "../../../../Content/C++/graph/queries/WaveletMatrixHeavyLightDecomposition.h"
#include "../../../../Content/C++/graph/representations/StaticGraph.h"
#include "../../../../Content/C++/datastructures/trees/fenwicktrees/BitFenwickTree.h"
using namespace std;

struct R1 {
  using Data = int;
  using Lazy = int;
  static Data qdef() { return 0; }
  static Data merge(const Data &l, const Data &r) { return l + r; }
  static Data invData(const Data &v) { return -v; }
  BitFenwickTree FT;
  R1(const vector<Data> &A) : FT(A.size()) {
    for (int i = 0; i < int(A.size()); i++) FT.set(i, A[i]);
    FT.build();
  }
  void update(int i, const Lazy &val) { FT.update(i, val); }
  Data query(int r) { return FT.query(r); }
};

struct R2 {
  using Data = int;
  using Lazy = int;
  static Data qdef() { return 0; }
  static Data merge(const Data &l, const Data &r) { return l + r; }
  BitFenwickTree FT;
  R2(const vector<Data> &A) : FT(A.size()) {
    for (int i = 0; i < int(A.size()); i++) FT.set(i, A[i]);
    FT.build();
  }
  void update(int i, const Lazy &val) { FT.update(i, val); }
  Data query(int l, int r) { return FT.query(l, r); }
};

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 5e4, MAXA = 100;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int V = rng() % 101;
    vector<int> A(V, 0);
    for (int v = 1; v < V; v++) A[v] = rng() % MAXA;
    vector<int> X(V, 0);
    for (int v = 1; v < V; v++) X[v] = rng() % 2;
    StaticGraph G(V);
    for (int v = 1; v < V; v++) G.addBiEdge(rng() % v, v);
    G.build();
    WaveletMatrixTreeAggregation<int, R1, true> wm(G, A, X);
    WaveletMatrixHLD<int, R2, true> hld(G, A, X);
    int Q = V <= 1 ? 0 : rng() % 101;
    vector<int> par(V), dep(V);
    function<void(int, int, int)> dfs = [&] (int v, int prev, int d) {
      par[v] = prev;
      dep[v] = d;
      for (int w : G[v]) if (w != prev) dfs(w, v, d + 1);
    };
    if (V > 0) dfs(0, -1, 0);
    auto getPath = [&] (int v, int w) {
      vector<int> ret, ret2;
      while (v != w) {
        if (dep[v] > dep[w]) {
          ret.push_back(v);
          v = par[v];
        } else {
          ret2.push_back(w);
          w = par[w];
        }
      }
      reverse(ret2.begin(), ret2.end());
      ret.insert(ret.end(), ret2.begin(), ret2.end());
      return ret;
    };
    vector<int> ans0, ans1, ans2;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 3;
      if (t == 0) {
        int v;
        do {
          v = rng() % V;
        } while (v == 0);
        wm.update(v, X[v] ^= 1);
        hld.update(v, X[v]);
      } else if (t == 1) {
        int v = rng() % V, w;
        do {
          w = rng() % V;
        } while (v == w);
        int a = rng() % MAXA, b = rng() % MAXA;
        if (a > b) swap(a, b);
        int sm = 0;
        for (int x : getPath(v, w)) if (a <= A[x] && A[x] <= b) sm += X[x];
        ans0.push_back(sm);
        ans1.push_back(wm.query(v, w, a, b));
        ans2.push_back(hld.query(v, w, a, b));
      } else {
        int v = rng() % V, w;
        do {
          w = rng() % V;
        } while (v == w);
        int k = rng() % ((wm.query(v, v, MAXA) + 1) * 2);
        vector<int> C;
        for (int x : getPath(v, w)) if (X[x]) C.push_back(A[x]);
        sort(C.begin(), C.end());
        if (k == 0) ans0.push_back(*min_element(A.begin(), A.end()));
        else if (k - 1 < int(C.size())) ans0.push_back(C[k - 1]);
        else ans0.push_back(INT_MAX);
        pair<bool, int *> p = wm.bsearch(v, w, [&] (int agg) {
          return agg >= k;
        });
        ans1.push_back(p.first ? *p.second : INT_MAX);
        p = hld.bsearch(v, w, [&] (int agg) {
          return agg >= k;
        });
        ans2.push_back(p.first ? *p.second : INT_MAX);
      }
    }
    assert(ans0 == ans1);
    assert(ans0 == ans2);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Values on Edges) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 5e4, MAXA = 100;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int V = rng() % 101;
    vector<int> A(V, 0);
    for (int v = 0; v < V; v++) A[v] = rng() % MAXA;
    vector<int> X(V, 0);
    for (int v = 0; v < V; v++) X[v] = rng() % 2;
    StaticGraph G(V);
    for (int v = 1; v < V; v++) G.addBiEdge(rng() % v, v);
    G.build();
    WaveletMatrixTreeAggregation<int, R1, false> wm(G, A, X);
    WaveletMatrixHLD<int, R2, false> hld(G, A, X);
    int Q = V == 0 ? 0 : rng() % 101;
    vector<int> par(V), dep(V);
    function<void(int, int, int)> dfs = [&] (int v, int prev, int d) {
      par[v] = prev;
      dep[v] = d;
      for (int w : G[v]) if (w != prev) dfs(w, v, d + 1);
    };
    if (V > 0) dfs(0, -1, 0);
    auto getPath = [&] (int v, int w) {
      vector<int> ret, ret2;
      while (v != w) {
        if (dep[v] > dep[w]) {
          ret.push_back(v);
          v = par[v];
        } else {
          ret2.push_back(w);
          w = par[w];
        }
      }
      ret.push_back(v);
      reverse(ret2.begin(), ret2.end());
      ret.insert(ret.end(), ret2.begin(), ret2.end());
      return ret;
    };
    vector<int> ans0, ans1, ans2;
    for (int i = 0; i < Q; i++) {
      int t = rng() % 3;
      if (t == 0) {
        int v = rng() % V;
        wm.update(v, X[v] ^= 1);
        hld.update(v, X[v]);
      } else if (t == 1) {
        int v = rng() % V, w = rng() % V;
        int a = rng() % MAXA, b = rng() % MAXA;
        if (a > b) swap(a, b);
        int sm = 0;
        for (int x : getPath(v, w)) if (a <= A[x] && A[x] <= b) sm += X[x];
        ans0.push_back(sm);
        ans1.push_back(wm.query(v, w, a, b));
        ans2.push_back(hld.query(v, w, a, b));
      } else {
        int v = rng() % V, w = rng() % V;
        int k = rng() % ((wm.query(v, v, MAXA) + 1) * 2);
        vector<int> C;
        for (int x : getPath(v, w)) if (X[x]) C.push_back(A[x]);
        sort(C.begin(), C.end());
        if (k == 0) ans0.push_back(*min_element(A.begin(), A.end()));
        else if (k - 1 < int(C.size())) ans0.push_back(C[k - 1]);
        else ans0.push_back(INT_MAX);
        pair<bool, int *> p = wm.bsearch(v, w, [&] (int agg) {
          return agg >= k;
        });
        ans1.push_back(p.first ? *p.second : INT_MAX);
        p = hld.bsearch(v, w, [&] (int agg) {
          return agg >= k;
        });
        ans2.push_back(p.first ? *p.second : INT_MAX);
      }
    }
    assert(ans0 == ans1);
    assert(ans0 == ans2);
    for (auto &&a : ans0) checkSum = 31 * checkSum + a;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Values on Vertices) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/components/StronglyConnectedComponents.h"
#include "../../../../Content/C++/graph/representations/StaticGraph.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int V = 2e6, E = 4e6;
  StaticGraph G(V);
  G.reserveDiEdges(E);
  for (int i = 0; i < E; i++) {
    int c = rng() % 100;
    int v = rng() % (V / 100) + (V / 100) * c, w = rng() % (V / 100) + (V / 100) * c;
    G.addDiEdge(v, w);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  vector<pair<int, int>> condensationEdges;
  SCC scc(G, condensationEdges);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v = 0; v < V; v++) checkSum = 31 * checkSum + scc.id[v];
  sort(condensationEdges.begin(), condensationEdges.end());
  for (auto &&e : condensationEdges) {
    checkSum = 31 * checkSum + e.first;
    checkSum = 31 * checkSum + e.second;
  }
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/components/BiconnectedComponents.h"
#include "../../../../Content/C++/graph/representations/StaticGraph.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int V = 2e6, E = 4e6;
  StaticGraph G(V);
  G.reserveDiEdges(E * 2);
  for (int i = 0; i < E; i++) {
    int c = rng() % 2;
    int v = rng() % (V / 2) + (V / 2) * c, w = rng() % (V / 2) + (V / 2) * c;
    G.addBiEdge(v, w);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  vector<pair<int, int>> blockCutForestEdges;
  BCC bcc(G, blockCutForestEdges);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v = 0; v < V; v++) {
    checkSum = 31 * checkSum + v;
    for (int id : bcc.ids[v]) checkSum = 31 * checkSum + id;
  }
  sort(blockCutForestEdges.begin(), blockCutForestEdges.end());
  for (auto &&e : blockCutForestEdges) {
    checkSum = 31 * checkSum + e.first;
    checkSum = 31 * checkSum + e.second;
  }
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/components/Bridges.h"
#include "../../../../Content/C++/graph/representations/StaticGraph.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int V = 2e6, E = 4e6;
  StaticGraph G(V);
  G.reserveDiEdges(E * 2);
  for (int i = 0; i < E; i++) {
    int c = rng() % 2;
    int v = rng() % (V / 2) + (V / 2) * c, w = rng() % (V / 2) + (V / 2) * c;
    G.addBiEdge(v, w);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  Bridges bridges(G);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v = 0; v < V; v++) checkSum = 31 * checkSum + bridges.id[v];
  sort(bridges.bridges.begin(), bridges.bridges.end());
  for (auto &&e : bridges.bridges) {
    checkSum = 31 * checkSum + e.first;
    checkSum = 31 * checkSum + e.second;
  }
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/components/ConnectedComponents.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  int V = 2e6, E = 4e6;
  CC cc(V);
  for (int i = 0; i < E; i++) {
    int c = rng() % 100;
    int v = rng() % (V / 100) + (V / 100) * c, w = rng() % (V / 100) + (V / 100) * c;
    cc.addEdge(v, w);
  }
  cc.assign();
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v = 0; v < V; v++) checkSum = 31 * checkSum + cc.id[v];
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/minimumspanningtree/ClassicalPrimMST.h"
#include "../../../../Content/C++/graph/minimumspanningtree/BoruvkaMST.h"
#include "../../../../Content/C++/graph/minimumspanningtree/KruskalMST.h"
#include "../../../../Content/C++/graph/minimumspanningtree/PrimMST.h"
#include "../../../../Content/C++/graph/representations/StaticGraph.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int V = 1e4, E = 5e6;
  vector<KruskalMST<long long>::Edge> edges;
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % (long long)(1e9) + 1;
    edges.emplace_back(v, w, weight);
  }
  const auto start_time = chrono::system_clock::now();
  KruskalMST<long long> mst(V, move(edges));
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Kruskal) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = mst.mstWeight;
  for (auto &&e : mst.mstEdges) if (get<0>(e) > get<1>(e)) swap(get<0>(e), get<1>(e));
  sort(mst.mstEdges.begin(), mst.mstEdges.end());
  for (auto &&e : mst.mstEdges) {
    checkSum = 31 * checkSum + get<0>(e);
    checkSum = 31 * checkSum + get<1>(e);
    checkSum = 31 * checkSum + get<2>(e);
  }
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  mt19937_64 rng(0);
  int V = 1e6, E = 5e6;
  vector<KruskalMST<long long>::Edge> edges;
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % (long long)(1e9) + 1;
    edges.emplace_back(v, w, weight);
  }
  const auto start_time = chrono::system_clock::now();
  KruskalMST<long long> mst(V, move(edges));
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Kruskal) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = mst.mstWeight;
  for (auto &&e : mst.mstEdges) if (get<0>(e) > get<1>(e)) swap(get<0>(e), get<1>(e));
  sort(mst.mstEdges.begin(), mst.mstEdges.end());
  for (auto &&e : mst.mstEdges) {
    checkSum = 31 * checkSum + get<0>(e);
    checkSum = 31 * checkSum + get<1>(e);
    checkSum = 31 * checkSum + get<2>(e);
  }
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  mt19937_64 rng(0);
  int V = 1e4, E = 5e6;
  vector<BoruvkaMST<long long>::Edge> edges;
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % (long long)(1e9) + 1;
    edges.emplace_back(v, w, weight);
  }
  const auto start_time = chrono::system_clock::now();
  BoruvkaMST<long long> mst(V, move(edges));
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (Boruvka) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = mst.mstWeight;
  for (auto &&e : mst.mstEdges) if (get<0>(e) > get<1>(e)) swap(get<0>(e), get<1>(e));
  sort(mst.mstEdges.begin(), mst.mstEdges.end());
  for (auto &&e : mst.mstEdges) {
    checkSum = 31 * checkSum + get<0>(e);
    checkSum = 31 * checkSum + get<1>(e);
    checkSum = 31 * checkSum + get<2>(e);
  }
  cout << "  Checksum: " << checkSum << endl;
}

void test4() {
  mt19937_64 rng(0);
  int V = 1e6, E = 5e6;
  vector<BoruvkaMST<long long>::Edge> edges;
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % (long long)(1e9) + 1;
    edges.emplace_back(v, w, weight);
  }
  const auto start_time = chrono::system_clock::now();
  BoruvkaMST<long long> mst(V, move(edges));
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 4 (Boruvka) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = mst.mstWeight;
  for (auto &&e : mst.mstEdges) if (get<0>(e) > get<1>(e)) swap(get<0>(e), get<1>(e));
  sort(mst.mstEdges.begin(), mst.mstEdges.end());
  for (auto &&e : mst.mstEdges) {
    checkSum = 31 * checkSum + get<0>(e);
    checkSum = 31 * checkSum + get<1>(e);
    checkSum = 31 * checkSum + get<2>(e);
  }
  cout << "  Checksum: " << checkSum << endl;
}

void test5() {
  mt19937_64 rng(0);
  int V = 1e4, E = 5e6;
  StaticWeightedGraph<long long> G(V);
  G.reserveDiEdges(E * 2);
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % (long long)(1e9) + 1;
    G.addBiEdge(v, w, weight);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  PrimMST<long long> mst(move(G));
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 5 (Prim) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = mst.mstWeight;
  for (auto &&e : mst.mstEdges) if (get<0>(e) > get<1>(e)) swap(get<0>(e), get<1>(e));
  sort(mst.mstEdges.begin(), mst.mstEdges.end());
  for (auto &&e : mst.mstEdges) {
    checkSum = 31 * checkSum + get<0>(e);
    checkSum = 31 * checkSum + get<1>(e);
    checkSum = 31 * checkSum + get<2>(e);
  }
  cout << "  Checksum: " << checkSum << endl;
}

void test6() {
  mt19937_64 rng(0);
  int V = 1e6, E = 5e6;
  StaticWeightedGraph<long long> G(V);
  G.reserveDiEdges(E * 2);
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % (long long)(1e9) + 1;
    G.addBiEdge(v, w, weight);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  PrimMST<long long> mst(move(G));
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 6 (Prim) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = mst.mstWeight;
  for (auto &&e : mst.mstEdges) if (get<0>(e) > get<1>(e)) swap(get<0>(e), get<1>(e));
  sort(mst.mstEdges.begin(), mst.mstEdges.end());
  for (auto &&e : mst.mstEdges) {
    checkSum = 31 * checkSum + get<0>(e);
    checkSum = 31 * checkSum + get<1>(e);
    checkSum = 31 * checkSum + get<2>(e);
  }
  cout << "  Checksum: " << checkSum << endl;
}

void test7() {
  mt19937_64 rng(0);
  int V = 1e4, E = 5e6;
  StaticWeightedGraph<long long> G(V);
  G.reserveDiEdges(E * 2);
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % (long long)(1e9) + 1;
    G.addBiEdge(v, w, weight);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  ClassicalPrimMST<long long> mst(move(G));
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 7 (Classical Prim) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = mst.mstWeight;
  for (auto &&e : mst.mstEdges) if (get<0>(e) > get<1>(e)) swap(get<0>(e), get<1>(e));
  sort(mst.mstEdges.begin(), mst.mstEdges.end());
  for (auto &&e : mst.mstEdges) {
    checkSum = 31 * checkSum + get<0>(e);
    checkSum = 31 * checkSum + get<1>(e);
    checkSum = 31 * checkSum + get<2>(e);
  }
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  test4();
  test5();
  test6();
  test7();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/bipartite/Bipartite.h"
#include "../../../../Content/C++/graph/bipartite/IncrementalBipartite.h"
#include "../../../../Content/C++/graph/representations/StaticGraph.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int V = 2e6, E = 4e6;
  StaticGraph G(V);
  G.reserveDiEdges(E * 2);
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    G.addBiEdge(v, w);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  Bipartite bp(G);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Bipartite) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = bp.bipartite;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  mt19937_64 rng(0);
  int V = 2e6, E = 4e6;
  IncrementalBipartite ibp(V);
  const auto start_time = chrono::system_clock::now();
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    ibp.addEdge(v, w);
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Incremental Bipartite) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = ibp.bipartiteGraph;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  mt19937_64 rng(0);
  int V = 2e6, E = 4e6;
  StaticGraph G(V);
  G.reserveDiEdges(E * 2);
  for (int i = 0; i < E; i++) {
    int v = rng() % (V / 2) * 2, w = rng() % (V / 2) * 2 + 1;
    G.addBiEdge(v, w);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  Bipartite bp(G);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (Bipartite) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = bp.bipartite;
  cout << "  Checksum: " << checkSum << endl;
}

void test4() {
  mt19937_64 rng(0);
  int V = 2e6, E = 4e6;
  IncrementalBipartite ibp(V);
  const auto start_time = chrono::system_clock::now();
  for (int i = 0; i < E; i++) {
    int v = rng() % (V / 2) * 2, w = rng() % (V / 2) * 2 + 1;
    ibp.addEdge(v, w);
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 4 (Incremental Bipartite) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = ibp.bipartiteGraph;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  test4();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/shortestpaths/ShortestHamiltonianCycle.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int V = rng() % 8, E = V == 0 ? 0 : rng() % (V * V);
    vector<vector<long long>> matrix(V, vector<long long>(V, LLONG_MAX));
    for (int i = 0; i < E; i++) {
      int v = rng() % V, w = rng() % V;
      long long weight = int(rng() % (int(2e9) + 1)) - int(1e9);
      matrix[v][w] = min(matrix[v][w], weight);
    }
    ShortestHamiltonianCycle<long long> shp(matrix);
    vector<int> P(V);
    iota(P.begin(), P.end(), 0);
    long long mn = LLONG_MAX;
    do {
      long long dist = 0;
      bool valid = true;
      for (int i = 0; valid && i < V; i++) {
        if (matrix[P[i]][P[(i + 1) % V]] == LLONG_MAX) valid = false;
        dist += matrix[P[i]][P[(i + 1) % V]];
      }
      if (valid) mn = min(mn, dist);
    } while (next_permutation(P.begin(), P.end()));
    assert(mn == shp.shortestCycleDist);
    if (shp.shortestCycleDist != LLONG_MAX) {
      long long checkDist = 0;
      for (int i = 0; i < V; i++) checkDist += matrix[shp.ord[i]][shp.ord[(i + 1) % V]];
      assert(shp.shortestCycleDist == checkDist);
    }
    checkSum = 31 * checkSum + shp.shortestCycleDist;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/shortestpaths/ShortestHamiltonianPath.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int V = rng() % 8, E = V == 0 ? 0 : rng() % (V * V);
    vector<vector<long long>> matrix(V, vector<long long>(V, LLONG_MAX));
    for (int i = 0; i < E; i++) {
      int v = rng() % V, w = rng() % V;
      long long weight = int(rng() % (int(2e9) + 1)) - int(1e9);
      matrix[v][w] = min(matrix[v][w], weight);
    }
    ShortestHamiltonianPath<long long> shp(matrix);
    vector<int> P(V);
    iota(P.begin(), P.end(), 0);
    long long mn = LLONG_MAX;
    do {
      long long dist = 0;
      bool valid = true;
      for (int i = 0; valid && i < V - 1; i++) {
        if (matrix[P[i]][P[i + 1]] == LLONG_MAX) valid = false;
        dist += matrix[P[i]][P[i + 1]];
      }
      if (valid) mn = min(mn, dist);
    } while (next_permutation(P.begin(), P.end()));
    assert(mn == shp.shortestPathDist);
    if (shp.shortestPathDist != LLONG_MAX) {
      long long checkDist = 0;
      for (int i = 0; i < V - 1; i++) checkDist += matrix[shp.ord[i]][shp.ord[i + 1]];
      assert(shp.shortestPathDist == checkDist);
    }
    checkSum = 31 * checkSum + shp.shortestPathDist;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/representations/StaticGraph.h"
#include "../../../../Content/C++/graph/shortestpaths/BellmanFordSSSP.h"
#include "../../../../Content/C++/graph/shortestpaths/ClassicalDijkstraSSSP.h"
#include "../../../../Content/C++/graph/shortestpaths/DijkstraSSSP.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int V = 1e4, E = 4e4;
  vector<tuple<int, int, long long>> edges;
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % int(1e9) + 1;
    edges.emplace_back(v, w, weight);
  }
  const auto start_time = chrono::system_clock::now();
  BellmanFordSSSP<long long> sssp(V, edges, 0);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Bellman Ford) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v = 0; v < V; v++) checkSum = 31 * checkSum + sssp.dist[v];
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  mt19937_64 rng(0);
  int V = 1e4, E = 4e4;
  StaticWeightedGraph<long long> G(V);
  G.reserveDiEdges(E);
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % int(1e9) + 1;
    G.addDiEdge(v, w, weight);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  ClassicalDijkstraSSSP<long long> sssp(G, 0);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Classical Dijkstra) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v = 0; v < V; v++) checkSum = 31 * checkSum + sssp.dist[v];
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  mt19937_64 rng(0);
  int V = 1e4, E = 4e6;
  StaticWeightedGraph<long long> G(V);
  G.reserveDiEdges(E);
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % int(1e9) + 1;
    G.addDiEdge(v, w, weight);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  ClassicalDijkstraSSSP<long long> sssp(G, 0);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (Classical Dijkstra) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v = 0; v < V; v++) checkSum = 31 * checkSum + sssp.dist[v];
  cout << "  Checksum: " << checkSum << endl;
}

void test4() {
  mt19937_64 rng(0);
  int V = 1e4, E = 4e4;
  StaticWeightedGraph<long long> G(V);
  G.reserveDiEdges(E);
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % int(1e9) + 1;
    G.addDiEdge(v, w, weight);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  DijkstraSSSP<long long> sssp(G, 0);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 4 (Dijkstra with PQ) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v = 0; v < V; v++) checkSum = 31 * checkSum + sssp.dist[v];
  cout << "  Checksum: " << checkSum << endl;
}

void test5() {
  mt19937_64 rng(0);
  int V = 1e4, E = 4e6;
  StaticWeightedGraph<long long> G(V);
  G.reserveDiEdges(E);
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % int(1e9) + 1;
    G.addDiEdge(v, w, weight);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  DijkstraSSSP<long long> sssp(G, 0);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 5 (Dijkstra with PQ) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v = 0; v < V; v++) checkSum = 31 * checkSum + sssp.dist[v];
  cout << "  Checksum: " << checkSum << endl;
}

void test6() {
  mt19937_64 rng(0);
  int V = 1e6, E = 4e6;
  StaticWeightedGraph<long long> G(V);
  G.reserveDiEdges(E);
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % int(1e9) + 1;
    G.addDiEdge(v, w, weight);
  }
  G.build();
  const auto start_time = chrono::system_clock::now();
  DijkstraSSSP<long long> sssp(G, 0);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 6 (Dijkstra with PQ) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v = 0; v < V; v++) checkSum = 31 * checkSum + sssp.dist[v];
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  test4();
  test5();
  test6();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/shortestpaths/FloydWarshallAPSP.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int V = 500, E = 2e4;
  vector<vector<long long>> matrix(V, vector<long long>(V, LLONG_MAX));
  for (int i = 0; i < E; i++) {
    int v = rng() % V, w = rng() % V;
    long long weight = rng() % int(1e9) + 1;
    matrix[v][w] = min(matrix[v][w], weight);
  }
  const auto start_time = chrono::system_clock::now();
  FloydWarshallAPSP<long long> apsp(matrix);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Floyd Warshall) Passed" << endl;
  cout << "  V: " << V << endl;
  cout << "  E: " << E << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int v = 0; v < V; v++) for (int w = 0; w < V; w++) checkSum = 31 * checkSum + apsp.dist[v][w];
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/graph/shortestpaths/FloydWarshallAPSP.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int V = rng() % 11, E = V == 0 ? 0 : rng() % (V * V);
    vector<vector<long long>> matrix(V, vector<long long>(V, LLONG_MAX));
    for (int i = 0; i < E; i++) {
      int v = rng() % V, w = rng() % V;
      long long weight = int(rng() % (int(2e9) + 1)) - int(1e9);
      matrix[v][w] = min(matrix[v][w], weight);
    }
    FloydWarshallAPSP<long long> apsp(matrix);
    for (int v = 0; v < V; v++) for (int w = 0; w < V; w++) {
      if (abs(apsp.dist[v][w]) != apsp.INF) {
        vector<tuple<int, int, long long>> path = apsp.getPath(v, w);
        long long sm = 0;
        for (auto &&e : path) {
          sm += get<2>(e);
          assert(get<2>(e) == matrix[get<0>(e)][get<1>(e)]);
        }
        assert(sm == apsp.dist[v][w]);
      }
      checkSum = 31 * checkSum + apsp.dist[v][w];
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/datastructures/unionfind/UnionFind.h"
#include "../../../../Content/C++/geometry/2d/Point.h"
#include "../../../../Content/C++/geometry/2d/Line.h"
#include "../../../../Content/C++/geometry/2d/Polygon.h"
#include "../../../../Content/C++/geometry/2d/PolygonTriangulation.h"
#include "../../../../Content/C++/graph/representations/AdjacencyListGraph.h"
using namespace std;

vector<pt> generatePolygon(int N, mt19937_64 &rng, bool grid) {
  vector<pt> P(N);
  assert(N >= 3);
  set<pt> seen;
  if (grid) {
    uniform_int_distribution<int> dis(0, 10);
    while (true) {
      for (auto &&p : P) {
        do {
          p.x = dis(rng);
          p.y = dis(rng);
        } while (seen.count(p));
        seen.insert(p);
      }
      sort(P.begin(), P.end());
      T sm = 0;
      for (int i = 0; i < N - 1; i++) sm += dist(P[i], P[i + 1]);
      if (!eq(sm, dist(P[0], P[N - 1]))) break;
    }
  } else {
    uniform_real_distribution<T> dis(0, 10);
    while (true) {
      for (auto &&p : P) {
        do {
          p.x = dis(rng);
          p.y = dis(rng);
        } while (seen.count(p));
        seen.insert(p);
      }
      sort(P.begin(), P.end());
      T sm = 0;
      for (int i = 0; i < N - 1; i++) sm += dist(P[i], P[i + 1]);
      if (!eq(sm, dist(P[0], P[N - 1]))) break;
    }
  }
  vector<pair<int, int>> edges;
  for (int i = 0; i < N; i++) for (int j = 0; j < i; j++) edges.emplace_back(i, j);
  sort(edges.begin(), edges.end(), [&] (const pair<int, int> &a, const pair<int, int> &b) {
    return dist(P[a.first], P[a.second]) < dist(P[b.first], P[b.second]);
  });
  UnionFind uf(N);
  AdjacencyListGraph G(N);
  for (auto &&e : edges) if (uf.join(e.first, e.second)) G.addBiEdge(e.first, e.second);
  for (int v = 0; v < N; v++) shuffle(G[v].begin(), G[v].end(), rng);
  vector<pt> ret;
  function<void(int, int)> dfs = [&] (int v, int prev) {
    ret.push_back(P[v]);
    for (int w : G[v]) if (w != prev) dfs(w, v);
  };
  dfs(0, -1);
  bool done = false;
  while (!done) {
    done = true;
    for (int i = 0; i < N; i++) for (int j = i + 2; j < N; j++) if (mod(j + 1, N) != i) {
      if (segSegIntersects(ret[i], ret[mod(i + 1, N)], ret[j], ret[mod(j + 1, N)])) {
        reverse(ret.begin() + i + 1, ret.begin() + j + 1);
        done = false;
      }
    }
  }
  return ret;
}

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e6;
  long long checkSum = 0;
  uniform_int_distribution<int> dis(3, 30);
  for (int ti = 0; ti < TESTCASES; ti++) {
    vector<pt> poly = generatePolygon(dis(rng), rng, false);
    if (isCcwPolygon(poly) == -1) reverse(poly.begin(), poly.end());
    T a2 = getArea2(poly), sm = 0;
    auto tris = polygonTriangulation(poly);
    assert(int(tris.size()) == int(poly.size()) - 2);
    for (auto &&t : tris) {
      T ta2 = area2(t[0], t[1], t[2]);
      assert(lt(0, ta2));
      sm += ta2;
    }
    assert(eq(a2, sm));
    checkSum += a2;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Random) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e6;
  long long checkSum = 0;
  uniform_int_distribution<int> dis(3, 30);
  for (int ti = 0; ti < TESTCASES; ti++) {
    vector<pt> poly = generatePolygon(dis(rng), rng, true);
    if (isCcwPolygon(poly) == -1) reverse(poly.begin(), poly.end());
    T a2 = getArea2(poly), sm = 0;
    auto tris = polygonTriangulation(poly);
    assert(int(tris.size()) == int(poly.size()) - 2);
    for (auto &&t : tris) {
      T ta2 = area2(t[0], t[1], t[2]);
      assert(lt(0, ta2));
      sm += ta2;
    }
    assert(eq(a2, sm));
    checkSum += a2;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Grid) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  const auto start_time = chrono::system_clock::now();
  long long checkSum = 0;
  vector<pt> poly = {pt(0, 0), pt(1, 0), pt(2, 0), pt(2, -1), pt(2, -2), pt(3, -2), pt(4, -2), pt(4, 0), pt(5, 0), pt(6, 0), pt(6, 1), pt(5, 1), pt(4, 1), pt(4, 3), pt(3, 3), pt(2, 3), pt(2, 2), pt(2, 1), pt(1, 1), pt(0, 1)};
  assert(int(poly.size()) == 20);
  T a2 = getArea2(poly), sm = 0;
  auto tris = polygonTriangulation(poly);
  assert(int(tris.size()) == int(poly.size()) - 2);
  for (auto &&t : tris) {
    T ta2 = area2(t[0], t[1], t[2]);
    assert(lt(0, ta2));
    sm += ta2;
  }
  assert(eq(a2, sm));
  checkSum += a2;
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (Special) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test4() {
  const auto start_time = chrono::system_clock::now();
  long long checkSum = 0;
  vector<pt> poly = {pt(6, 5), pt(0, 5), pt(0, 4), pt(1, 4), pt(1, 3), pt(0, 3), pt(0, 2), pt(1, 2), pt(1, 1), pt(0, 1), pt(0, 0), pt(6, 0), pt(6, 1), pt(5, 1), pt(5, 2), pt(6, 2), pt(6, 3), pt(5, 3), pt(5, 4), pt(6, 4)};
  assert(int(poly.size()) == 20);
  T a2 = getArea2(poly), sm = 0;
  auto tris = polygonTriangulation(poly);
  assert(int(tris.size()) == int(poly.size()) - 2);
  for (auto &&t : tris) {
    T ta2 = area2(t[0], t[1], t[2]);
    assert(lt(0, ta2));
    sm += ta2;
  }
  assert(eq(a2, sm));
  checkSum += a2;
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 4 (Special) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  test4();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/geometry/2d/BentleyOttmann.h"
#include "../../../../Content/C++/geometry/2d/Line.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 5e4;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    vector<pair<pt, pt>> segs;
    for (int i = 0; i < 10; i++) {
      T a, b, c;
      do {
        a = int(rng() % 21) - 10;
        b = int(rng() % 21) - 10;
        c = int(rng() % 401) - 201;
      } while (a == 0 && b == 0);
      Line l(a, b, c);
      while (rng() % 2) {
        pt p = l.proj(pt(int(rng() % 21) - 10, int(rng() % 21) - 10));
        pt q = l.proj(pt(int(rng() % 21) - 10, int(rng() % 21) - 10));
        segs.emplace_back(p, q);
      }
    }
    set<pair<int, int>> ans0, ans1;
    bentleyOttmann(segs, [&] (int i, int j) {
      if (i > j) swap(i, j);
      ans0.emplace(i, j);
    });
    for (int i = 0; i < int(segs.size()); i++) for (int j = i + 1; j < int(segs.size()); j++) {
      if (segSegIntersects(segs[i].first, segs[i].second, segs[j].first, segs[j].second)) ans1.emplace(i, j);
    }
    assert(ans0 == ans1);
    for (auto &&p : ans0) {
      checkSum = 31 * checkSum + p.first;
      checkSum = 31 * checkSum + p.second;
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/geometry/2d/FarthestPair.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e6;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 7;
    vector<pt> P(N);
    for (auto &&p : P) p = pt(int(rng() % int(10) - int(5)), int(rng() % int(10) - int(5)));
    FarthestPair fp(P);
    T mx = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < i; j++) mx = max(mx, distSq(P[i], P[j]));
    assert(eq(mx, fp.bestDistSq));
    checkSum = 31 * checkSum + fp.bestDistSq;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/geometry/2d/MinTriangleArea.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 2e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 11;
    vector<pt> P(N);
    for (auto &&p : P) p = pt(rng() % int(10), rng() % int(10));
    T minArea2 = numeric_limits<T>::max();
    for (int i = 0; i < N; i++) for (int j = 0; j < i; j++) for (int k = 0; k < j; k++)
      minArea2 = min(minArea2, abs(area2(P[i], P[j], P[k])));
    MinTriangleArea mta(P);
    assert(minArea2 == mta.minArea2);
    if (minArea2 != numeric_limits<T>::max()) assert(area2(mta.PA, mta.PB, mta.PC) == minArea2);
    checkSum = 31 * checkSum + minArea2;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../../Content/C++/geometry/2d/Line.h"
#include "../../../../Content/C++/geometry/2d/Angle.h"
#include "../../../../Content/C++/geometry/2d/Circle.h"
#include "../../../../Content/C++/geometry/2d/Polygon.h"
#include "../../../../Content/C++/geometry/2d/IncrementalConvexHull.h"
using namespace std;

vector<pt> generateConvexPolygon(int N, mt19937_64 &rng) {
  uniform_real_distribution<T> dis(0, 1);
  vector<T> X(N), Y(N);
  for (int i = 0; i < N; i++) X[i] = dis(rng);
  for (int i = 0; i < N; i++) Y[i] = dis(rng);
  sort(X.begin(), X.end());
  sort(Y.begin(), Y.end());
  T xmin = X[0], xmax = X[N - 1], ymin = Y[0], ymax = Y[N - 1];
  vector<T> xv, yv;
  T lastTop = xmin, lastBot = xmin;
  for (int i = 1; i < N - 1; i++) {
    if (rng() % 2) {
      xv.push_back(X[i] - lastTop);
      lastTop = X[i];
    } else {
      xv.push_back(lastBot - X[i]);
      lastBot = X[i];
    }
  }
  xv.push_back(xmax - lastTop);
  xv.push_back(lastBot - xmax);
  T lastLeft = ymin, lastRight = ymin;
  for (int i = 1; i < N - 1; i++) {
    if (rng() % 2) {
      yv.push_back(Y[i] - lastLeft);
      lastLeft = Y[i];
    } else {
      yv.push_back(lastRight - Y[i]);
      lastRight = Y[i];
    }
  }
  yv.push_back(ymax - lastLeft);
  yv.push_back(lastRight - ymax);
  shuffle(yv.begin(), yv.end(), rng);
  vector<pt> V(N), P;
  for (int i = 0; i < N; i++) V[i] = pt(xv[i], yv[i]);
  sort(V.begin(), V.end(), [&] (pt a, pt b) {
    return Angle(a) < Angle(b);
  });
  T x = 0, xminPoly = 0, y = 0, yminPoly = 0;
  for (int i = 0; i < N; i++) {
    P.emplace_back(x, y);
    xminPoly = min(xminPoly, x += V[i].x);
    yminPoly = min(yminPoly, y += V[i].y);
  }
  x = xmin - xminPoly;
  y = ymin - yminPoly;
  for (int i = 0; i < N; i++) P[i] += pt(x, y);
  for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
    assert(segSegIntersects(P[i], P[mod(i + 1, N)], P[j], P[mod(j + 1, N)]) != 1);
  if (N == 2) assert(P[0] != P[1]);
  if (N >= 3) for (int i = 0; i < N; i++) assert(ccw(P[mod(i + N - 1, N)], P[i], P[mod(i + 1, N)]) > 0);
  return P;
}

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 5e4;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 10 + 1;
    vector<pt> poly = generateConvexPolygon(N, rng);
    IncrementalConvexHull ch;
    for (auto &&p : poly) assert(ch.addPoint(p));
    int Q = 100;
    uniform_real_distribution<T> dis(-10, 10);
    for (int i = 0; i < Q; i++) {
      pt p;
      do {
        p = pt(dis(rng), dis(rng));
      } while (isInConvexPolygon(poly, p) >= 0);
      if (N >= 2 && rng() % 10 == 0) {
        int j = rng() % N;
        int k = mod(j + 1, N);
        if (rng() % 2) swap(j, k);
        p = poly[j] * T(2) - poly[k];
      }
      pair<int, int> tangent = convexPolygonPointTangent(poly, p);
      assert(0 <= tangent.first && tangent.first < N);
      assert(0 <= tangent.second && tangent.second < N);
      checkSum = 31 * checkSum + tangent.first;
      checkSum = 31 * checkSum + tangent.second;
      if (N == 1) {
        assert(tangent.first == tangent.second);
      } else if (N == 2) {
        if (tangent.first == tangent.second) assert(ccw(poly[0], poly[1], p) == 0);
      } else assert(tangent.first != tangent.second);
      Line l1(p, poly[tangent.first]), l2(p, poly[tangent.second]);
      for (int j = 0; j < N; j++) {
        assert(l1.onLeft(poly[j]) < 0 || (l1.onLeft(poly[j]) == 0 && le(distSq(p, poly[tangent.first]), distSq(p, poly[j]))));
        assert(l2.onLeft(poly[j]) > 0 || (l2.onLeft(poly[j]) == 0 && le(distSq(p, poly[tangent.second]), distSq(p, poly[j]))));
      }
      auto tangent2 = ch.pointTangents(p);
      assert(poly[tangent.first] == tangent2.first->p);
      assert(poly[tangent.second] == tangent2.second->p);
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Convex Polygon Point Tangent) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 5e3;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 10 + 1;
    vector<pt> poly = generateConvexPolygon(N, rng);
    IncrementalConvexHull ch;
    for (auto &&p : poly) assert(ch.addPoint(p));
    int Q = 100;
    uniform_real_distribution<T> dis(-10, 10), dis2(0, 10);
    for (int i = 0; i < Q; i++) {
      pt p;
      do {
        p = pt(dis(rng), dis(rng));
      } while (isInConvexPolygon(poly, p) >= 0);
      if (N >= 2 && rng() % 10 == 0) {
        int j = rng() % N;
        int k = mod(j + 1, N);
        if (rng() % 2) swap(j, k);
        p = poly[j] * T(2) - poly[k];
      }
      T r;
      int iter = 0;
      auto good = [&] {
        if (iter++ >= 100000) {
          do {
            p = pt(dis(rng), dis(rng));
          } while (isInConvexPolygon(poly, p) >= 0);
          iter = 0;
        }
        if (gt(polygonCircleIntersectionArea(poly, Circle(p, r)), 0)) return false;
        for (int j = 0; j < N; j++) if (Circle(p, r).contains(poly[j]) >= 0) return false;
        if (N > 1) for (int j = 0; j < N; j++) {
          vector<pt> inter = circleLineIntersection(Circle(p, r), Line(poly[j], poly[mod(j + 1, N)]));
          if (!inter.empty() && !segSegIntersection(poly[j], poly[mod(j + 1, N)], inter[0], inter.back()).empty()) return false;
        }
        return true;
      };
      do {
        r = dis2(rng);
      } while (!good());
      if (rng() % 10 == 0) r = 0;
      bool inner = rng() % 2;
      Circle c(p, r);
      pair<int, int> tangent = convexPolygonCircleTangent(poly, c, inner);
      assert(0 <= tangent.first && tangent.first < N);
      assert(0 <= tangent.second && tangent.second < N);
      checkSum = 31 * checkSum + tangent.first;
      checkSum = 31 * checkSum + tangent.second;
      if (N == 1) {
        assert(tangent.first == tangent.second);
      }
      if (r == 0) {
        assert(tangent == convexPolygonPointTangent(poly, p));
      } else {
        vector<pair<pt, pt>> t1, t2;
        circleCircleTangent(Circle(poly[tangent.first], 0), c, inner, t1);
        circleCircleTangent(Circle(poly[tangent.second], 0), c, inner, t2);
        pt a = t1[0].second, b = t2[1].second;
        Line l1(a, poly[tangent.first]), l2(b, poly[tangent.second]);
        if (inner) {
          assert(eq(circleHalfPlaneIntersectionArea(c, Line(-l1.v, -l1.c)), 0));
          assert(eq(circleHalfPlaneIntersectionArea(c, l2), 0));
        } else {
          assert(eq(circleHalfPlaneIntersectionArea(c, l1), 0));
          assert(eq(circleHalfPlaneIntersectionArea(c, Line(-l2.v, -l2.c)), 0));
        }
        for (int j = 0; j < N; j++) {
          assert(l1.onLeft(poly[j]) < 0 || (l1.onLeft(poly[j]) == 0 && le(distSq(a, poly[tangent.first]), distSq(a, poly[j]))));
          assert(l2.onLeft(poly[j]) > 0 || (l2.onLeft(poly[j]) == 0 && le(distSq(b, poly[tangent.second]), distSq(b, poly[j]))));
        }
      }
      auto tangent2 = ch.circleTangents(c, inner);
      assert(poly[tangent.first] == tangent2.first->p);
      assert(poly[tangent.second] == tangent2.second->p);
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Convex Polygon Circle Tangent) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 10 + 1, M = rng() % 10 + 1;
    bool inner = rng() % 2;
    vector<pt> poly1 = generateConvexPolygon(N, rng), poly2 = generateConvexPolygon(M, rng);
    pt add = rng() % 2 ? pt(1, 0) : pt(0, 1);
    for (auto &&p : poly2) p += add;
    if (rng() % 2) {
      swap(N, M);
      swap(poly1, poly2);
    }
    IncrementalConvexHull ch1, ch2;
    for (auto &&p : poly1) assert(ch1.addPoint(p));
    for (auto &&p : poly2) assert(ch2.addPoint(p));
    vector<pair<int, int>> tangent = convexPolygonConvexPolygonTangent(poly1, poly2, inner);
    assert(0 <= tangent[0].first && tangent[0].first < N);
    assert(0 <= tangent[1].first && tangent[1].first < N);
    assert(0 <= tangent[0].second && tangent[0].second < M);
    assert(0 <= tangent[1].second && tangent[1].second < M);
    checkSum = 31 * checkSum + tangent[0].first;
    checkSum = 31 * checkSum + tangent[0].second;
    checkSum = 31 * checkSum + tangent[1].first;
    checkSum = 31 * checkSum + tangent[1].second;
    pt a = poly1[tangent[0].first], b = poly1[tangent[1].first], c = poly2[tangent[0].second], d = poly2[tangent[1].second];
    Line l1(a, c), l2(b, d);
    for (int i = 0; i < N; i++) {
      assert(l1.onLeft(poly1[i]) > 0 || (l1.onLeft(poly1[i]) == 0 && le(distSq(c, a), distSq(c, poly1[i]))));
      assert(l2.onLeft(poly1[i]) < 0 || (l2.onLeft(poly1[i]) == 0 && le(distSq(d, b), distSq(d, poly1[i]))));
    }
    for (int i = 0; i < M; i++) {
      assert(l1.onLeft(poly2[i]) == (inner ? -1 : 1) || (l1.onLeft(poly2[i]) == 0 && le(distSq(a, c), distSq(a, poly2[i]))));
      assert(l2.onLeft(poly2[i]) == (inner ? 1 : -1) || (l2.onLeft(poly2[i]) == 0 && le(distSq(b, d), distSq(b, poly2[i]))));
    }
    auto tangent2 = ch1.hullTangents(ch2, inner);
    assert(a == tangent2[0].first->p);
    assert(b == tangent2[1].first->p);
    assert(c == tangent2[0].second->p);
    assert(d == tangent2[1].second->p);
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (Convex Polygon Convex Polygon Tangent) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test4() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 5e4;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 10 + 1;
    vector<pt> poly = generateConvexPolygon(N, rng);
    IncrementalConvexHull ch;
    for (auto &&p : poly) assert(ch.addPoint(p));
    int Q = 100;
    uniform_real_distribution<T> dis(-10, 10);
    for (int i = 0; i < Q; i++) {
      pt p;
      do {
        p = pt(dis(rng), dis(rng));
      } while (isInConvexPolygon(poly, p) >= 0);
      if (N >= 2 && rng() % 10 == 0) {
        int j = rng() % N;
        int k = mod(j + 1, N);
        if (rng() % 2) swap(j, k);
        p = poly[j] * T(2) - poly[k];
      }
      pt closest = closestPointOnConvexPolygon(poly, p);
      for (int j = 0; j < N; j++) {
        pt q = closestPtOnSeg(p, poly[j], poly[mod(j + 1, N)]);
        assert(le(distSq(p, closest), distSq(p, q)));
      }
      checkSum = 31 * checkSum + distSq(p, closest);
      pt closest2 = ch.closestPt(p);
      assert(eq(distSq(closest, closest2), 0));
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 4 (Closest Point on Convex Polygon) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test5() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 5e4;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 10 + 1;
    vector<pt> poly = generateConvexPolygon(N, rng);
    IncrementalConvexHull ch;
    for (auto &&p : poly) assert(ch.addPoint(p));
    int Q = 100;
    uniform_real_distribution<T> dis(-10, 10);
    for (int i = 0; i < Q; i++) {
      pt p;
      do {
        p = pt(dis(rng), dis(rng));
      } while (isInConvexPolygon(poly, p) >= 0);
      pt q;
      do {
        q = pt(dis(rng), dis(rng));
      } while (isInConvexPolygon(poly, p) >= 0);
      if (N >= 2 && rng() % 10 == 0) {
        int j = rng() % N;
        p = poly[j];
        if (rng() % 2) q = poly[mod(j + 1, N)];
      }
      Line l(p, q);
      pair<int, int> sides = convexPolygonLineIntersection(poly, l);
      vector<pt> ans0, ans1, ans2 = ch.lineIntersection(l);
      auto addToVec = [&] (vector<pt> &v, int i) {
        pt a = poly[i], b = poly[mod(i + 1, N)];
        if (a != b) {
          pt c;
          lineLineIntersection(l, Line(a, b), c);
          if (onSeg(c, a, b)) v.push_back(c);
        }
        if (l.onLeft(a) == 0) v.push_back(a);
        if (l.onLeft(b) == 0) v.push_back(b);
      };
      auto clean = [&] (vector<pt> &v) {
        sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
      };
      if (sides.first != -1) addToVec(ans1, sides.first);
      if (sides.second != -1) addToVec(ans1, sides.second);
      for (int j = 0; j < N; j++) addToVec(ans0, j);
      clean(ans0);
      clean(ans1);
      assert(ans0 == ans1);
      assert(ans0 == ans2);
      for (pt a : ans0) {
        checkSum = 31 * checkSum + 1e9 * a.x;
        checkSum = 31 * checkSum + 1e9 * a.y;
      }
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 5 (Line Convex Polygon Intersection) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  test4();
  test5();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/dp/LongestIncreasingSubsequence.h"
#include "../../../Content/C++/dp/LongestIncreasingSubsequenceFenwick.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int N = 1e7;
  vector<int> A(N);
  for (auto &&a : A) a = rng() % int(6) + 1;
  const auto start_time = chrono::system_clock::now();
  vector<int> inds = longestIncreasingSubsequence(A);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (lower_bound) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int i : inds) checkSum = 31 * checkSum + i;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  mt19937_64 rng(0);
  int N = 1e7;
  vector<int> A(N);
  for (auto &&a : A) a = rng() % int(6) + 1;
  const auto start_time = chrono::system_clock::now();
  vector<int> inds = longestIncreasingSubsequenceFenwick(A);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Fenwick) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (int i : inds) checkSum = 31 * checkSum + i;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/dp/SubsetSum.h"
using namespace std;

const int M = 100;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 11;
    vector<int> A(N);
    for (auto &&a : A) a = rng() % int(10) + 1;
    bitset<M + 1> possible = subsetSum<M>(A);
    int tot = accumulate(A.begin(), A.end(), 0);
    vector<int> cnt(tot + 1, 0), dp = subsetSumCount<int>(A, tot);
    for (int mask = 0; mask < (1 << N); mask++) {
      int sm = 0;
      for (int i = 0; i < N; i++) if ((mask >> i) & 1) sm += A[i];
      cnt[sm]++;
    }
    assert(cnt == dp);
    for (int i = 0; i < int(cnt.size()); i++) assert(possible[i] == bool(cnt[i]));
    for (int i : dp) checkSum = 31 * checkSum + i;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/dp/MultisubsetSum.h"
using namespace std;

void test1() {
  mt19937_64 rng(0);
  int N = 3e4, M = 3e4;
  vector<int> A(N);
  for (auto &&a : A) a = rng() % int(1e3) + 1;
  const auto start_time = chrono::system_clock::now();
  auto dp = multisubsetSum<bool>(A, M);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (bool) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&i : dp) checkSum = 31 * checkSum + i;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  mt19937_64 rng(0);
  int N = 3e4, M = 3e4;
  vector<int> A(N);
  for (auto &&a : A) a = rng() % int(1e3) + 1;
  const auto start_time = chrono::system_clock::now();
  auto dp = multisubsetSum<char>(A, M);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (char) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&i : dp) checkSum = 31 * checkSum + i;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  mt19937_64 rng(0);
  int N = 3e4, M = 3e4;
  vector<int> A(N);
  for (auto &&a : A) a = rng() % int(1e3) + 1;
  const auto start_time = chrono::system_clock::now();
  auto dp = multisubsetSum<int>(A, M);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (int) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  long long checkSum = 0;
  for (auto &&i : dp) checkSum = 31 * checkSum + i;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/dp/LongestIncreasingSubsequence.h"
#include "../../../Content/C++/dp/LongestIncreasingSubsequenceFenwick.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 7;
    vector<int> A(N);
    for (auto &&a : A) a = rng() % int(6) + 1;
    vector<int> maxInds;
    for (int mask = 1; mask < (1 << N); mask++) {
      vector<int> inds;
      for (int i = 0; i < N; i++) if ((mask >> i) & 1) inds.push_back(i);
      bool good = true;
      for (int i = 0; i < int(inds.size()) - 1 && good; i++) good &= A[inds[i]] < A[inds[i + 1]];
      if (good && make_pair(int(inds.size()), inds) > make_pair(int(maxInds.size()), maxInds)) maxInds = inds;
    }
    vector<int> inds = longestIncreasingSubsequence(A);
    assert(inds == maxInds);
    for (int i : inds) checkSum = 31 * checkSum + i;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (lower_bound) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 7;
    vector<int> A(N);
    for (auto &&a : A) a = rng() % int(6) + 1;
    vector<int> minB;
    for (int mask = 1; mask < (1 << N); mask++) {
      vector<int> B;
      for (int i = 0; i < N; i++) if ((mask >> i) & 1) B.push_back(A[i]);
      bool good = true;
      for (int i = 0; i < int(B.size()) - 1 && good; i++) good &= B[i] < B[i + 1];
      if (good && make_pair(-int(B.size()), B) < make_pair(-int(minB.size()), minB)) minB = B;
    }
    vector<int> inds = longestIncreasingSubsequenceFenwick(A), B;
    for (int i : inds) B.push_back(A[i]);
    assert(B == minB);
    for (int i : inds) checkSum = 31 * checkSum + i;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Fenwick) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/math/Combinatorics.h"
#include "../../../Content/C++/math/ModularArithmetic.h"
using namespace std;

const long long MOD1 = 1e9, MOD2 = 1e9 + 7;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e6;
  const int N = 20;
  long long checkSum = 0;
  vector<long long> ans0, ans1, ans2;
  Combinatorics<long long> C(N);
  for (int ti = 0; ti < TESTCASES; ti++) {
    long long n = rng() % (N + 1);
    ans0.push_back(factorial(n) % MOD1);
    ans1.push_back(factorialMod(n, MOD1));
    ans2.push_back(C.factorial(n) % MOD1);
    checkSum = 31 * checkSum + ans0.back();
  }
  assert(ans0 == ans1);
  assert(ans0 == ans2);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 (Factorial Mod) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test2() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e6;
  const int N = 50;
  long long checkSum = 0;
  vector<long long> ans0, ans1;
  CombinatoricsModPrime<long long> C(N, MOD2);
  for (int ti = 0; ti < TESTCASES; ti++) {
    long long n = rng() % (N + 1);
    ans0.push_back(factorialMod(n, MOD2));
    ans1.push_back(C.factorial(n));
    assert(mulMod(C.factorial(n), C.invFactorial(n), MOD2) == 1);
    checkSum = 31 * checkSum + ans0.back();
  }
  assert(ans0 == ans1);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 2 (Factorial Mod Prime) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test3() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e6;
  const int N = 20;
  long long checkSum = 0;
  vector<long long> ans0, ans1, ans2, ans3;
  Combinatorics<long long> C(N);
  for (int ti = 0; ti < TESTCASES; ti++) {
    long long n = rng() % (N + 1), k = rng() % (n + 1);
    ans0.push_back(factorial(n) / factorial(n - k) % MOD1);
    ans1.push_back(permute(n, k) % MOD1);
    ans2.push_back(permuteMod(n, k, MOD1));
    ans3.push_back(C.permute(n, k) % MOD1);
    checkSum = 31 * checkSum + ans0.back();
  }
  assert(ans0 == ans1);
  assert(ans0 == ans2);
  assert(ans0 == ans3);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 3 (Permute Mod) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test4() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e6;
  const int N = 50;
  long long checkSum = 0;
  vector<long long> ans0, ans1, ans2;
  CombinatoricsModPrime<long long> C(N, MOD2);
  for (int ti = 0; ti < TESTCASES; ti++) {
    long long n = rng() % (N + 1), k = rng() % (n + 1);
    ans0.push_back(divModPrime(factorialMod(n, MOD2), factorialMod(n - k, MOD2), MOD2));
    ans1.push_back(permuteMod(n, k, MOD2));
    ans2.push_back(C.permute(n, k));
    checkSum = 31 * checkSum + ans0.back();
  }
  assert(ans0 == ans1);
  assert(ans0 == ans2);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 4 (Permute Mod Prime) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test5() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e6;
  const int N = 20;
  long long checkSum = 0;
  vector<long long> ans0, ans1, ans2;
  Combinatorics<long long> C(N);
  for (int ti = 0; ti < TESTCASES; ti++) {
    if (rng() % 2) {
      long long n = rng() % (N + 1), k = rng() % (n + 1);
      ans0.push_back(factorial(n) / factorial(n - k) / factorial(k));
      ans1.push_back(choose(n, k));
      ans2.push_back(C.choose(n, k));
    } else {
      long long n = rng() % (N / 2) + 1, k = rng() % (N / 2);
      ans0.push_back(factorial(n + k - 1) / factorial(n - 1) / factorial(k));
      ans1.push_back(multiChoose(n, k));
      ans2.push_back(C.multiChoose(n, k));
    }
    checkSum = 31 * checkSum + ans0.back();
  }
  assert(ans0 == ans1);
  assert(ans0 == ans2);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 5 (Combinations) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test6() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e6;
  const int N = 50;
  long long checkSum = 0;
  vector<long long> ans0, ans1, ans2;
  CombinatoricsModPrime<long long> C(N, MOD2);
  for (int ti = 0; ti < TESTCASES; ti++) {
    if (rng() % 2) {
      long long n = rng() % (N + 1), k = rng() % (n + 1);
      ans0.push_back(divModPrime(divModPrime(factorialMod(n, MOD2), factorialMod(n - k, MOD2), MOD2), factorialMod(k, MOD2), MOD2));
      ans1.push_back(chooseModPrime(n, k, MOD2));
      ans2.push_back(C.choose(n, k));
    } else {
      long long n = rng() % (N / 2) + 1, k = rng() % (N / 2);
      ans0.push_back(divModPrime(divModPrime(factorialMod(n + k - 1, MOD2), factorialMod(n - 1, MOD2), MOD2), factorialMod(k, MOD2), MOD2));
      ans1.push_back(multiChooseModPrime(n, k, MOD2));
      ans2.push_back(C.multiChoose(n, k));
    }
    checkSum = 31 * checkSum + ans0.back();
  }
  assert(ans0 == ans1);
  assert(ans0 == ans2);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 6 (Combinations Mod Prime) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test7() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int N = 20;
  long long checkSum = 0;
  Combinatorics<long long> C(N);
  vector<vector<long long>> A = pascalsTriangle<long long>(N), B = pascalsTriangleMod<long long>(N, MOD1);
  for (int i = 0; i <= N; i++) {
    assert(A[i] == pascalsRow<long long>(i));
    for (int j = 0; j <= i; j++) {
      assert(A[i][j] % MOD1 == C.choose(i, j) % MOD1);
      assert(A[i][j] % MOD1 == B[i][j]);
      checkSum = checkSum * 31 + A[i][j];
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 7 (Pascal's Triangle Mod) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test8() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int N = 1000;
  long long checkSum = 0;
  CombinatoricsModPrime<long long> C(N, MOD2);
  vector<vector<long long>> A = pascalsTriangleMod<long long>(N, MOD2);
  for (int i = 0; i <= N; i++) {
    assert(A[i] == pascalsRowModPrime<long long>(i, MOD2));
    for (int j = 0; j <= i; j++) {
      assert(A[i][j] == C.choose(i, j));
      checkSum = checkSum * 31 + A[i][j];
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 8 (Pascal's Triangle Mod Prime) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test9() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e6;
  const int N = 20;
  long long checkSum = 0;
  vector<long long> ans0, ans1;
  for (int ti = 0; ti < TESTCASES; ti++) {
    if (rng() % 2) {
      long long n = rng() % (N + 1);
      long long sm = 0;
      for (long long i = 0; i <= n; i++) sm += i;
      ans0.push_back(sm);
      ans1.push_back(sumTo(n));
    } else {
      long long a = rng() % (N + 1), b = rng() % (N + 1);
      if (a > b) swap(a, b);
      long long sm = 0;
      for (long long i = a; i <= b; i++) sm += i;
      ans0.push_back(sm);
      ans1.push_back(sumBetween(a, b));
    }
    checkSum = checkSum * 31 + ans0.back();
  }
  assert(ans0 == ans1);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 9 (Summation) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test10() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e6;
  const int N = 20, MAXVAL = 1e6;
  long long checkSum = 0;
  vector<long long> ans0, ans1;
  for (int ti = 0; ti < TESTCASES; ti++) {
    long long a1 = rng() % (MAXVAL * 2 + 1) - MAXVAL;
    long long d = rng() % (MAXVAL * 2 + 1) - MAXVAL;
    int n = rng() % N + 1;
    long long v = a1, sm = a1;
    for (int i = 2; i <= n; i++) {
      v += d;
      sm += v;
    }
    ans0.push_back(v);
    ans1.push_back(arithSeq(a1, d, n));
    checkSum = checkSum * 31 + ans0.back();
    ans0.push_back(sm);
    ans1.push_back(arithSeries(a1, d, n));
    checkSum = checkSum * 31 + ans0.back();
  }
  assert(ans0 == ans1);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 10 (Arithmetic Sequence) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

void test11() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e6;
  const int N = 10, MAXVAL = 10;
  long long checkSum = 0;
  vector<long long> ans0, ans1;
  for (int ti = 0; ti < TESTCASES; ti++) {
    long long a1 = rng() % (MAXVAL * 2 + 1) - MAXVAL;
    long long r = rng() % (MAXVAL * 2 + 1) - MAXVAL;
    int n = rng() % N + 1;
    long long v = a1, sm = a1;
    for (int i = 2; i <= n; i++) {
      v *= r;
      sm += v;
    }
    ans0.push_back(v);
    ans1.push_back(geoSeq(a1, r, n));
    checkSum = checkSum * 31 + ans0.back();
    ans0.push_back(sm);
    ans1.push_back(geoSeries(a1, r, n));
    checkSum = checkSum * 31 + ans0.back();
  }
  assert(ans0 == ans1);
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 11 (Geometric Sequence) Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  test2();
  test3();
  test4();
  test5();
  test6();
  test7();
  test8();
  test9();
  test10();
  test11();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/math/Matrix.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e4, OPS = 10;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 11, M = rng() % 11;
    Matrix<long long> A = makeMatrix<long long>(N, M), B = A;
    for (int k = 0; k < OPS; k++) {
      Matrix<long long> C = makeMatrix<long long>(N, M);
      for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) C[i][j] = rng() % int(1e9);
      A = A + C;
      B = B - C;
      for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) checkSum = 31 * checkSum + A[i][j];
      for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) checkSum = 31 * checkSum + B[i][j];
    }
    assert((A + B) == makeMatrix<long long>(N, M));
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/math/Nimber.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e3;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    uint64_t a = 0;
    while (a == 0) a = rng();
    uint64_t inv = mulInvNim(a);
    assert(mulNim(a, inv) == 1);
    checkSum = 31 * checkSum + inv;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/math/GCD.h"
using namespace std;

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int m = rng() % 100 + 1, a = rng() % m, c = rng() % m;
    pair<int, int> x = solveCongruence(a, c, m);
    for (int i = 0; i < 1000; i++) assert((a * i % m == c) == (i % x.second == x.first));
    checkSum = 31 * checkSum + x.first;
    checkSum = 31 * checkSum + x.second;
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}


text:
#include <bits/stdc++.h>
#include "../../../Content/C++/string/LongestCommonPrefix.h"
#include "../../../Content/C++/string/SuffixArray.h"
#include "../../../Content/C++/string/SAISSuffixArray.h"
using namespace std;

int lcp(const vector<int> &A, const vector<int> &B) {
  int i = 0;
  for (; i < min(int(A.size()), int(B.size())); i++) if (A[i] != B[i]) break;
  return i;
}

vector<int> suffix(const vector<int> &A, int i) {
  return vector<int>(A.begin() + i, A.end());
}

void test1() {
  const auto start_time = chrono::system_clock::now();
  mt19937_64 rng(0);
  const int TESTCASES = 1e5;
  long long checkSum = 0;
  for (int ti = 0; ti < TESTCASES; ti++) {
    int N = rng() % 11;
    vector<int> A(N, 0);
    for (auto &&a : A) a = rng() % int(10) + 1e5;
    LongestCommonPrefix<SuffixArray<int>> LCP1(A);
    LongestCommonPrefix<SAISSuffixArray<int>> LCP2(A);
    vector<pair<vector<int>, int>> suffixes;
    for (int i = 0; i < N; i++) suffixes.emplace_back(suffix(A, i), i);
    sort(suffixes.begin(), suffixes.end());
    vector<int> inv(N, -1);
    for (int i = 0; i < N; i++) {
      assert(suffixes[i].second == LCP1.SA.ind[i]);
      assert(suffixes[i].second == LCP2.SA.ind[i]);
      inv[suffixes[i].second] = i;
      checkSum = 31 * checkSum + LCP1.SA.ind[i];
    }
    for (int i = 0; i < N; i++) {
      assert(inv[i] == LCP1.SA.rnk[i]);
      assert(inv[i] == LCP2.SA.rnk[i]);
      checkSum = 31 * checkSum + LCP1.SA.rnk[i];
    }
    for (int i = 0; i < N - 1; i++) {
      assert(lcp(suffixes[i].first, suffixes[i + 1].first) == LCP1.SA.LCP[i]);
      assert(lcp(suffixes[i].first, suffixes[i + 1].first) == LCP2.SA.LCP[i]);
      checkSum = 31 * checkSum + LCP1.SA.LCP[i];
    }
    if (N > 0) {
      assert(LCP1.SA.LCP[N - 1] == 0);
      assert(LCP2.SA.LCP[N - 1] == 0);
    }
    for (int i = 0; i < N; i++) for (int j = i; j < N; j++) {
      assert(lcp(suffix(A, i), suffix(A, j)) == LCP1.lcp(i, j));
      assert(lcp(suffix(A, i), suffix(A, j)) == LCP2.lcp(i, j));
      checkSum = 31 * checkSum + LCP1.lcp(i, j);
    }
  }
  const auto end_time = chrono::system_clock::now();
  double sec = ((end_time - start_time).count() / double(chrono::system_clock::period::den));
  cout << "Subtest 1 Passed" << endl;
  cout << "  Time: " << fixed << setprecision(3) << sec << "s" << endl;
  cout << "  Checksum: " << checkSum << endl;
}

int main() {
  test1();
  cout << "Test Passed" << endl;
  return 0;
}