merge mzuenni changes

126 files changed, 3543 insertions, 757 deletions

diff --git a/.github/workflows/list_missing.yml b/.github/workflows/list_missing.yml
index 48cbe03..0ed7e01 100644
--- a/.github/workflows/list_missing.yml
+++ b/.github/workflows/list_missing.yml
@@ -1,9 +1,21 @@
 on: [push, pull_request]
 
 jobs:
-  pdf:
+  missing:
     name: List missing
     runs-on: ubuntu-latest
     steps:
       - uses: actions/checkout@v4
       - run: ./test/test.sh --missing
+      - run: ./test/test.sh --coverage >> $GITHUB_ENV
+      - uses: schneegans/dynamic-badges-action@v1.7.0
+        with:
+          auth: ${{ secrets.GIST_COVERAGE_SECRET }}
+          gistID: 73fb3c58350c58b623f221fc237def62
+          filename: tcr_coverage.json
+          label: coverage
+          message: ${{ env.COVERED }}/${{ env.TOTAL }}
+          namedLogo: GitHub
+          valColorRange: ${{ env.TOTAL }}
+          minColorRange: ${{ env.REQUIRED }}
+          maxColorRange: ${{ env.TOTAL }}
diff --git a/.github/workflows/test_all.yml b/.github/workflows/test_all.yml
index eddc002..bb2489b 100644
--- a/.github/workflows/test_all.yml
+++ b/.github/workflows/test_all.yml
@@ -2,13 +2,13 @@ on:
   workflow_dispatch:
 
 jobs:
-  pdf:
+  all:
     strategy:
       matrix:
         os: [ubuntu-latest, ubuntu-22.04]
     name: Test all (${{ matrix.os }})
     runs-on: ${{ matrix.os }}
-    timeout-minutes: 10
+    timeout-minutes: 20
     steps:
       - uses: actions/checkout@v4
       - run: ./test/test.sh
diff --git a/.github/workflows/test_datastructures.yml b/.github/workflows/test_datastructures.yml
index 9e58389..dffcf0a 100644
--- a/.github/workflows/test_datastructures.yml
+++ b/.github/workflows/test_datastructures.yml
@@ -10,7 +10,7 @@ on:
   workflow_dispatch:
 
 jobs:
-  pdf:
+  datastructures:
     strategy:
       matrix:
         os: [ubuntu-latest, ubuntu-22.04]
diff --git a/.github/workflows/test_geometry.yml b/.github/workflows/test_geometry.yml
index c1cc95d..fc45e5c 100644
--- a/.github/workflows/test_geometry.yml
+++ b/.github/workflows/test_geometry.yml
@@ -10,7 +10,7 @@ on:
   workflow_dispatch:
 
 jobs:
-  pdf:
+  geometry:
     strategy:
       matrix:
         os: [ubuntu-latest, ubuntu-22.04]
diff --git a/.github/workflows/test_graph.yml b/.github/workflows/test_graph.yml
index b402d21..505707c 100644
--- a/.github/workflows/test_graph.yml
+++ b/.github/workflows/test_graph.yml
@@ -10,7 +10,7 @@ on:
   workflow_dispatch:
 
 jobs:
-  pdf:
+  graph:
     strategy:
       matrix:
         os: [ubuntu-latest, ubuntu-22.04]
diff --git a/.github/workflows/test_math.yml b/.github/workflows/test_math.yml
index 6df75db..ef759c0 100644
--- a/.github/workflows/test_math.yml
+++ b/.github/workflows/test_math.yml
@@ -10,7 +10,7 @@ on:
   workflow_dispatch:
 
 jobs:
-  pdf:
+  math:
     strategy:
       matrix:
         os: [ubuntu-latest, ubuntu-22.04]
diff --git a/.github/workflows/test_other.yml b/.github/workflows/test_other.yml
index 07592d5..14c0550 100644
--- a/.github/workflows/test_other.yml
+++ b/.github/workflows/test_other.yml
@@ -10,7 +10,7 @@ on:
   workflow_dispatch:
 
 jobs:
-  pdf:
+  other:
     strategy:
       matrix:
         os: [ubuntu-latest, ubuntu-22.04]
diff --git a/.github/workflows/test_pdf.yml b/.github/workflows/test_pdf.yml
index e1d660b..ab273f7 100644
--- a/.github/workflows/test_pdf.yml
+++ b/.github/workflows/test_pdf.yml
@@ -10,12 +10,9 @@ on:
   workflow_dispatch:
 
 jobs:
-  pdf:
-    strategy:
-      matrix:
-        os: [ubuntu-latest, ubuntu-22.04]
-    name: Test pdf (${{ matrix.os }})
-    runs-on: ${{ matrix.os }}
+  pdf_22-04:
+    name: Test pdf (ubuntu-22.04)
+    runs-on: ubuntu-22.04
     timeout-minutes: 5
     steps:
       - uses: actions/checkout@v4
@@ -23,3 +20,20 @@ jobs:
           sudo apt-get update
           sudo apt-get install latexmk texlive-latex-base texlive-latex-recommended texlive-latex-extra texlive-lang-german texlive-fonts-extra
       - run: make
+
+  pdf_latest:
+    name: Test pdf (ubuntu-latest)
+    runs-on: ubuntu-22.04
+    timeout-minutes: 5
+    steps:
+      - uses: actions/checkout@v4
+      - run: |
+          sudo apt-get update
+          sudo apt-get install latexmk texlive-latex-base texlive-latex-recommended texlive-latex-extra texlive-lang-german texlive-fonts-extra
+      - run: make
+      - uses: exuanbo/actions-deploy-gist@v1
+        with:
+          token: ${{ secrets.GIST_COVERAGE_SECRET }}
+          gist_id: 73fb3c58350c58b623f221fc237def62
+          file_path: tcr.pdf
+          file_type: binary
diff --git a/.github/workflows/test_string.yml b/.github/workflows/test_string.yml
index 8ca5e1b..0d79040 100644
--- a/.github/workflows/test_string.yml
+++ b/.github/workflows/test_string.yml
@@ -10,7 +10,7 @@ on:
   workflow_dispatch:
 
 jobs:
-  pdf:
+  string:
     strategy:
       matrix:
         os: [ubuntu-latest, ubuntu-22.04]
diff --git a/.github/workflows/test_template.yml b/.github/workflows/test_template.yml
index 827b9ac..01f57bb 100644
--- a/.github/workflows/test_template.yml
+++ b/.github/workflows/test_template.yml
@@ -10,7 +10,7 @@ on:
   workflow_dispatch:
 
 jobs:
-  pdf:
+  template:
     strategy:
       matrix:
         os: [ubuntu-latest, ubuntu-22.04]
diff --git a/.gitignore b/.gitignore
index 9742c1f..01e9771 100644
--- a/.gitignore
+++ b/.gitignore
@@ -224,5 +224,6 @@ TSWLatexianTemp*
 # files produced by the testing system
 *.test
 *.ok
-*.tmp.cpp
 *.d
+# ignore build test awk files
+test/awk/*
diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex
index a0eea64..4bbe507 100644
--- a/content/datastructures/datastructures.tex
+++ b/content/datastructures/datastructures.tex
@@ -52,7 +52,7 @@
 		\method{insert}{fügt wert $\mathit{val}$ an stelle $i$ ein (verschiebt alle Positionen $\geq i$)}{\log(n)}
 		\method{remove}{löscht werte $[i,i+\mathit{count})$}{\log(n)}
 	\end{methods}
-	\sourcecode{datastructures/treap2.cpp}
+	\sourcecode{datastructures/treap.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Range Minimum Query}
diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index 2bd67a6..7148e31 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -1,22 +1,22 @@
 struct Line {
-	mutable ll m, b, p;
+	mutable ll m, c, p;
 	bool operator<(const Line& o) const {return m < o.m;}
 	bool operator<(ll x) const {return p < x;}
 };
 
-struct HullDynamic : multiset<Line, less<>> {
-	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
-	ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);}
+struct HullDynamic : multiset<Line, less<>> { // max über Geraden
+	// (for doubles, use INF = 1/.0, div(a,c) = a/c)
+	ll div(ll a, ll c) {return a / c - ((a ^ c) < 0 && a % c);}
 
 	bool isect(iterator x, iterator y) {
 		if (y == end()) {x->p = INF; return false;}
-		if (x->m == y->m) x->p = x->b > y->b ? INF : -INF;
-		else x->p = div(y->b - x->b, x->m - y->m);
+		if (x->m == y->m) x->p = x->c > y->c ? INF : -INF;
+		else x->p = div(y->c - x->c, x->m - y->m);
 		return x->p >= y->p;
 	}
 
-	void add(ll m, ll b) {
-		auto x = insert({m, b, 0});
+	void add(ll m, ll c) {
+		auto x = insert({m, c, 0});
 		while (isect(x, next(x))) erase(next(x));
 		if (x != begin()) {
 			--x;
@@ -29,6 +29,6 @@ struct HullDynamic : multiset<Line, less<>> {
 
 	ll query(ll x) {
 		auto l = *lower_bound(x);
-		return l.m * x + l.b;
+		return l.m * x + l.c;
 	}
 };
diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp
index f66778e..1318ca7 100644
--- a/content/datastructures/lichao.cpp
+++ b/content/datastructures/lichao.cpp
@@ -8,13 +8,13 @@ struct Fun { // Default: Linear function. Change as needed.
 
 // Default: Computes min. Change lines with comment for max.
 struct Lichao {
-	static constexpr Fun id = {0, inf}; // {0, -inf}
+	static constexpr Fun id = {0, INF}; // {0, -INF}
 	int n, cap;
 	vector<Fun> seg;
-	Lichao() : n(sz(xs)), cap(2<<__lg(n)), seg(2*cap, id) {}
+	Lichao() : n(sz(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {}
 	
 	void _insert(Fun f, int l, int r, int i) {
-		while (i < 2*cap){
+		while (i < 2 * cap) {
 			int m = (l+r)/2;
 			if (m >= n) {r = m; i = 2*i; continue;}
 			Fun &g = seg[i];
@@ -26,7 +26,7 @@ struct Lichao {
 
 	void _segmentInsert(Fun f, int l, int r, int a, int b, int i) {
 		if (l <= a && b <= r) _insert(f, a, b, i);
-		else if (a < r && l < b){
+		else if (a < r && l < b) {
 			int m = (a+b)/2;
 			_segmentInsert(f, l, r, a, m, 2*i);
 			_segmentInsert(f, l, r, m, b, 2*i+1);
@@ -36,7 +36,7 @@ struct Lichao {
 	}
 
 	ll _query(int x) {
-		ll ans = inf; // -inf
+		ll ans = INF; // -INF
 		for (int i = x + cap; i > 0; i /= 2) {
 			ans = min(ans, seg[i](x)); // max
 		}
diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
index e7b9b3e..2bdeccf 100644
--- a/content/datastructures/monotonicConvexHull.cpp
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -16,7 +16,7 @@ struct Envelope {
 			ls.pop_back();
 		}
 		ls.push_back({m, b});
-		ptr = min(ptr, sz(ls) - 1);
+		ptr = min(ptr, (int)sz(ls) - 1);
 	}
 
 	ll query(ll x) {
diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp
index d00b635..734bf91 100644
--- a/content/datastructures/pbds.cpp
+++ b/content/datastructures/pbds.cpp
@@ -15,10 +15,10 @@ using Tree = tree<T, null_type, less<T>, rb_tree_tag,
 T.order_of_key(x); // number of elements strictly less than x
 auto it = T.find_by_order(k); // k-th element
 
+constexpr uint64_t RNG = ll(2e18 * acos(-1)) | 199; // random odd
 template<typename T> struct chash {
-	static const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd
 	size_t operator()(T o) const {
-		return __builtin_bswap64(hash<T>()(o) * C);
+		return __builtin_bswap64(hash<T>()(o) * RNG);
 }};
 template<typename K, typename V>
 using hashMap = gp_hash_table<K, V, chash<K>>;
diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp
index 4093cdc..f26680d 100644
--- a/content/datastructures/persistent.cpp
+++ b/content/datastructures/persistent.cpp
@@ -4,15 +4,15 @@ struct persistent {
 	vector<pair<int, T>> data;

 

 	persistent(int& time, T value = {}) 

-		: time(time), data(1, {time, value}) {}

+		: time(time), data(1, {2*time, value}) {}

 	

 	T get(int t) {

-		return prev(upper_bound(all(data), pair{t+1, T{}}))->second;

+		return prev(upper_bound(all(data),pair{2*t+1, T{}}))->second;

 	}

 	

 	int set(T value) {

-		time += 2;

-		data.push_back({time, value});

+		time++;

+		data.push_back({2*time, value});

 		return time;

 	}

 };

diff --git a/content/datastructures/persistentArray.cpp b/content/datastructures/persistentArray.cpp
index 60d8b17..8326700 100644
--- a/content/datastructures/persistentArray.cpp
+++ b/content/datastructures/persistentArray.cpp
@@ -10,8 +10,8 @@ struct persistentArray {
 	T get(int p, int t) {return data[p].get(t);}

 

 	int set(int p, T value) {

-		mods.push_back({p, time});

-		return data[p].set(value);

+		mods.push_back({p, data[p].set(value)});

+		return mods.back().second;

 	}

 

 	void reset(int t) {

diff --git a/content/datastructures/treap.cpp b/content/datastructures/treap.cpp
index c96e36a..c5a60e9 100644
--- a/content/datastructures/treap.cpp
+++ b/content/datastructures/treap.cpp
@@ -1,79 +1,79 @@
-struct node {
-	int key, prio, left, right, size;
-	node(int key, int prio) : key(key), prio(prio), left(-1),
-	                          right(-1), size(1) {};
-};
+mt19937 rng(0xc4bd5dad);
+struct Treap {
+	struct Node {
+		ll val;
+		int prio, size = 1, l = -1, r = -1;
+		Node(ll x) : val(x), prio(rng()) {}
+	};
 
-vector<node> treap;
+	vector<Node> treap;
+	int root = -1;
 
-int getSize(int root) {
-	return root < 0 ? 0 : treap[root].size;
-}
+	int getSize(int v) {
+		return v < 0 ? 0 : treap[v].size;
+	}
 
-void update(int root) {
-	if (root < 0) return;
-	treap[root].size = 1 + getSize(treap[root].left)
-	                     + getSize(treap[root].right);
-}
+	void upd(int v) {
+		if (v < 0) return;
+		auto& V = treap[v];
+		V.size = 1 + getSize(V.l) + getSize(V.r);
+		// Update Node Code
+	}
 
-pair<int, int> split(int root, int minKeyRight) {
-	if (root < 0) return {-1, -1};
-	if (treap[root].key >= minKeyRight) {
-		auto leftSplit = split(treap[root].left, minKeyRight);
-		treap[root].left = leftSplit.second;
-		update(root);
-		leftSplit.second = root;
-		return leftSplit;
-	} else {
-		auto rightSplit = split(treap[root].right, minKeyRight);
-		treap[root].right = rightSplit.first;
-		update(root);
-		rightSplit.first = root;
-		return rightSplit;
-}}
+	void push(int v) {
+		if (v < 0) return;
+		//auto& V = treap[v];
+		//if (V.lazy) {
+		//	Lazy Propagation Code
+		//	if (V.l >= 0) treap[V.l].lazy = true;
+		//	if (V.r >= 0) treap[V.r].lazy = true;
+		//	V.lazy = false;
+		//}
+	}
 
-int merge (int left, int right) {
-	if (left < 0) return right;
-	if (right < 0) return left;
-	if (treap[left].prio < treap[right].prio) { //min priority heap
-		treap[left].right = merge(treap[left].right, right);
-		update(left);
-		return left;
-	} else {
-		treap[right].left = merge(left, treap[right].left);
-		update(right);
-		return right;
-}}
+	pair<int, int> split(int v, int k) {
+		if (v < 0) return {-1, -1};
+		auto& V = treap[v];
+		push(v);
+		if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k)
+			auto [left, right] = split(V.l, k);
+			V.l = right;
+			upd(v);
+			return {left, v};
+		} else {
+			// and only "k"
+			auto [left, right] = split(V.r, k - getSize(V.l) - 1);
+			V.r = left;
+			upd(v);
+			return {v, right};
+	}}
 
-//insert values with high priority first
-int insert(int root, int key, int prio) {
-	int next = sz(treap);
-	treap.emplace_back(key, prio);
-	auto t = split(root, key);
-	//returns new root
-	return merge(merge(t.first, next), t.second);
-}
+	int merge(int left, int right) {
+		if (left < 0) return right;
+		if (right < 0) return left;
+		if (treap[left].prio < treap[right].prio) {
+			push(left);
+			treap[left].r = merge(treap[left].r, right);
+			upd(left);
+			return left;
+		} else {
+			push(right);
+			treap[right].l = merge(left, treap[right].l);
+			upd(right);
+			return right;
+	}}
 
-int remove(int root, int key) {
-	if (root < 0) return -1;
-	if (key < treap[root].key) {
-		treap[root].left = remove(treap[root].left, key);
-		update(root);
-		return root;
-	} else if (key > treap[root].key) {
-		treap[root].right = remove(treap[root].right, key);
-		update(root);
-		return root;
-	} else { //check prio?
-		return merge(treap[root].left, treap[root].right);
-}}
+	void insert(int i, ll val) { // and i = val
+		auto [left, right] = split(root, i);
+		treap.emplace_back(val);
+		left = merge(left, sz(treap) - 1);
+		root = merge(left, right);
+	}
 
-int kth(int root, int k) {
-	if (root < 0) return -1;
-	int leftSize = getSize(treap[root].left);
-	if (k < leftSize) return kth(treap[root].left, k);
-	else if (k > leftSize) {
-		return kth(treap[root].right, k - 1 - leftSize);
+	void remove(int i, int count = 1) {
+		auto [left, t_right] = split(root, i);
+		auto [middle, right] = split(t_right, count);
+		root = merge(left, right);
 	}
-	return root;
-}
+	// for query use remove and read middle BEFORE remerging
+};
diff --git a/content/datastructures/treap2.cpp b/content/datastructures/treap2.cpp
deleted file mode 100644
index e40da0d..0000000
--- a/content/datastructures/treap2.cpp
+++ /dev/null
@@ -1,79 +0,0 @@
-mt19937 rng(0xc4bd5dad);
-struct Treap {
-	struct Node {
-		ll val;
-		int prio, size = 1, l = -1, r = -1;
-		Node(ll x): val(x), prio(rng()) {}
-	};
-
-	vector<Node> treap;
-	int root = -1;
-
-	int getSize(int v) {
-		return v < 0 ? 0 : treap[v].size;
-	}
-
-	void upd(int v) {
-		if (v < 0) return;
-		auto &V = treap[v];
-		V.size = 1 + getSize(V.l) + getSize(V.r);
-		// Update Node Code
-	}
-
-	void push(int v) {
-		if (v < 0) return;
-		//auto &V = treap[v];
-		//if (V.lazy) {
-		//	Lazy Propagation Code
-		//	if (V.l >= 0) treap[V.l].lazy = true;
-		//	if (V.r >= 0) treap[V.r].lazy = true;
-		//	V.lazy = false;
-		//}
-	}
-
-	pair<int, int> split(int v, int k) {
-		if (v < 0) return {-1, -1};
-		auto &V = treap[v];
-		push(v);
-		if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k)
-			auto [left, right] = split(V.l, k);
-			V.l = right;
-			upd(v);
-			return {left, v};
-		} else {
-			// and only "k"
-			auto [left, right] = split(V.r, k - getSize(V.l) - 1);
-			V.r = left;
-			upd(v);
-			return {v, right};
-	}}
-
-	int merge(int left, int right) {
-		if (left < 0) return right;
-		if (right < 0) return left;
-		if (treap[left].prio < treap[right].prio) {
-			push(left);
-			treap[left].r = merge(treap[left].r, right);
-			upd(left);
-			return left;
-		} else {
-			push(right);
-			treap[right].l = merge(left, treap[right].l);
-			upd(right);
-			return right;
-	}}
-
-	void insert(int i, ll val) { // and i = val
-		auto [left, right] = split(root, i);
-		treap.emplace_back(val);
-		left = merge(left, ssize(treap) - 1);
-		root = merge(left, right);
-	}
-
-	void remove(int i, int count = 1) {
-		auto [left, t_right] = split(root, i);
-		auto [middle, right] = split(t_right, count);
-		root = merge(left, right);
-	}
-	// for query use remove and read middle BEFORE remerging
-};
diff --git a/content/geometry/convexHull.cpp b/content/geometry/convexHull.cpp
index 6d89e05..1173924 100644
--- a/content/geometry/convexHull.cpp
+++ b/content/geometry/convexHull.cpp
@@ -11,8 +11,8 @@ vector<pt> convexHull(vector<pt> pts){
 			while (k > t && cross(h[k-2], h[k-1], *it) <= 0) k--;
 			h[k++] = *it;
 	}};
-	half(all(pts), 1);// Untere Hülle.
-	half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle.
+	half(all(pts), 1); // Untere Hülle.
+	half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle.
 	h.resize(k);
 	return h;
 }
diff --git a/content/geometry/formulas3d.cpp b/content/geometry/formulas3d.cpp
index dee3ce8..63de2ce 100644
--- a/content/geometry/formulas3d.cpp
+++ b/content/geometry/formulas3d.cpp
@@ -26,23 +26,23 @@ int ccw(pt3 a, pt3 b, pt3 c, pt3 p) {
 	return (orien > EPS) - (orien < -EPS);
 }
 
-// Entfernung von Punkt p zur Ebene a,b,c.
+// Entfernung von Punkt p zur Ebene a, b, c.
 double distToPlane(pt3 a, pt3 b, pt3 c, pt3 p) {
-	pt3 n = cross(b-a, c-a);
-	return (abs(dot(n, p)) - dot(n, a)) / abs(n);
+	pt3 n = cross(b - a, c - a);
+	return abs(dot(n, a - p)) / abs(n);
 }
 
-// Liegt p in der Ebene a,b,c?
+// Liegt p in der Ebene a, b, c?
 bool pointOnPlane(pt3 a, pt3 b, pt3 c, pt3 p) {
 	return ccw(a, b, c, p) == 0;
 }
 
-// Schnittpunkt von der Grade a-b und der Ebene c,d,e
+// Schnittpunkt von der Grade a-b und der Ebene c, d, e
 // die Grade darf nicht parallel zu der Ebene sein!
 pt3 linePlaneIntersection(pt3 a, pt3 b, pt3 c, pt3 d, pt3 e) {
-	pt3 n = cross(d-c, e-c);
-	pt3 d = b - a;
-	return a - d * (dot(n, a) - dot(n, c)) / dot(n, d);
+	pt3 n = cross(d - c, e - c);
+	pt3 dir = b - a;
+	return a + dir * dot(n, c - a) / dot(n, dir);
 }
 
 // Abstand zwischen der Grade a-b und c-d
diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp
index 3509e0e..02c71e3 100644
--- a/content/geometry/hpi.cpp
+++ b/content/geometry/hpi.cpp
@@ -1,4 +1,4 @@
-constexpr ll inf = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP
+constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF; //THIS CODE IS WIP
 
 bool left(pt p) {return real(p) < 0 || 
 					   (real(p) == 0 && imag(p) < 0);}
@@ -27,22 +27,22 @@ struct hp {
 			if (ort == 0) return cross(from, to, a.from) < 0;
 			return cross(b.dir(), a.dir()) * ort > 0;
 		}
-		ll y = cross(a.dir(), b.dir());
-		ll z = cross(b.from - a.from, b.dir());
-		ptl i = mul(y, a.from) + mul(z, a.dir()); //intersect a and b
-		// check if i is outside/right of x
-		return imag(conj(mul(sgn(y),dir()))*(i-mul(y,from))) < 0;
+		ll x = cross(a.dir(), b.dir());
+		ll y = cross(b.from - a.from, b.dir());
+		ptl i = mul(x, a.from) + mul(y, a.dir()); //intersect a and b
+		// check if i is outside/right of this
+		return imag(conj(mul(sgn(x),dir()))*(i-mul(x,from))) < 0;
 	}
 };
 
 constexpr ll lim = 2e9+7;
 
 deque<hp> intersect(vector<hp> hps) {
-	hps.push_back(hp(pt{lim+1,-1}));
-	hps.push_back(hp(pt{lim+1,1}));
+	hps.push_back(hp(pt{lim + 1, -1}));
+	hps.push_back(hp(pt{lim + 1, 1}));
 	sort(all(hps));
 
-	deque<hp> dq = {hp(pt{-lim, 1})};
+	deque<hp> dq = {hp(pt{-lim - 1, 1})};
 	for (auto x : hps) {
 		while (sz(dq) > 1 && x.check(dq.end()[-1], dq.end()[-2]))
 			dq.pop_back();
@@ -60,7 +60,7 @@ deque<hp> intersect(vector<hp> hps) {
 
 	while (sz(dq) > 2 && dq[0].check(dq.end()[-1], dq.end()[-2]))
 		dq.pop_back();
-	while (sz(dq) > 2 && dq.end()[-1].check(dq[0], dq[1]))
+	while (sz(dq) > 2 && dq.back().check(dq[0], dq[1]))
 		dq.pop_front();
 
 	if (sz(dq) < 3) return {};
diff --git a/content/geometry/lines.cpp b/content/geometry/lines.cpp
index 95536a4..36de1db 100644
--- a/content/geometry/lines.cpp
+++ b/content/geometry/lines.cpp
@@ -1,10 +1,10 @@
 struct line {
-	double a, b, c; // ax + by + c = 0; vertikale Line: b = 0, sonst: b = 1
-	line(pt p, pt q) : a(-imag(q-p)), b(real(q-p)), c(cross({b, -a},p)) {}
+	double a, b, c; // ax + by + c = 0; vertikale Gerade: b = 0
+	line(pt p, pt q) : a(imag(p-q)), b(real(q-p)), c(cross({-b, a}, p)) {}
 };
 
-line pointsToLine(pt p1, pt p2) {
-	line l;
+line pointsToLine(pt p1, pt p2) { // vertikale Gerade: b = 1 oder b = 0
+	line l(0, 0);
 	if (abs(real(p1 - p2)) < EPS) {
 		l.a = 1; l.b = 0.0; l.c = -real(p1);
 	} else {
@@ -15,19 +15,19 @@ line pointsToLine(pt p1, pt p2) {
 	return l;
 }
 
-bool parallel(line l1, line l2) {
+bool parallel(line l1, line l2) { // braucht b in {0, 1}
 	return (abs(l1.a - l2.a) < EPS) && (abs(l1.b - l2.b) < EPS);
 }
 
-bool same(line l1, line l2) {
+bool same(line l1, line l2) { // braucht b in {0, 1}
 	return parallel(l1, l2) && (abs(l1.c - l2.c) < EPS);
 }
 
-bool intersect(line l1, line l2, pt& p) {
+bool intersect(line l1, line l2, pt& res) { // braucht b in {0, 1}
 	if (parallel(l1, l2)) return false;
 	double y, x = (l2.b * l1.c - l1.b * l2.c) / (l2.a * l1.b - l1.a * l2.b);
 	if (abs(l1.b) > EPS) y = -(l1.a * x + l1.c);
 	else y = -(l2.a * x + l2.c);
-	p = {x, y};
+	res = {x, y};
 	return true;
 }
diff --git a/content/geometry/linesAndSegments.cpp b/content/geometry/linesAndSegments.cpp
index 1e21cba..ddab554 100644
--- a/content/geometry/linesAndSegments.cpp
+++ b/content/geometry/linesAndSegments.cpp
@@ -5,7 +5,7 @@ bool pointOnLine(pt a, pt b, pt p) {
 
 // Test auf Linienschnitt zwischen a-b und c-d. (nicht identisch)
 bool lineIntersection(pt a, pt b, pt c, pt d) {
-	return abs(cross(a - b, c - d)) < EPS;
+	return abs(cross(a - b, c - d)) > EPS;
 }
 
 // Berechnet den Schnittpunkt der Graden a-b und c-d.
diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp
index 3178290..064d81f 100644
--- a/content/geometry/polygon.cpp
+++ b/content/geometry/polygon.cpp
@@ -29,7 +29,7 @@ bool inside(pt p, const vector<pt>& poly) {
 	bool in = false;
 	for (int i = 0; i + 1 < sz(poly); i++) {
 		pt a = poly[i], b = poly[i + 1];
-		if (pointOnLineSegment(a, b, p)) return false;
+		if (pointOnSegment(a, b, p)) return false;
 		if (real(a) > real(b)) swap(a,b);
 		if (real(a) <= real(p) && real(p) < real(b) &&
 		    cross(p, a, b) < 0) {
diff --git a/content/geometry/segmentIntersection.cpp b/content/geometry/segmentIntersection.cpp
index 4262ddc..afc01b2 100644
--- a/content/geometry/segmentIntersection.cpp
+++ b/content/geometry/segmentIntersection.cpp
@@ -18,8 +18,8 @@ struct event {
 	int id, type;
 	bool operator<(const event& o) const {
 		if (real(p) != real(o.p)) return real(p) < real(o.p);
-		if (type != o.type) return type > o.type;
-		return imag(p) < imag(o.p);
+		if (imag(p) != imag(o.p)) return imag(p) < imag(o.p);
+		return type > o.type;
 	}
 };
 
@@ -29,7 +29,7 @@ bool lessPT(const pt& a, const pt& b) {
 }
 
 bool intersect(const seg& a, const seg& b) {
-	return lineSegmentIntersection(a.a, a.b, b.a, b.b);
+	return segmentIntersection(a.a, a.b, b.a, b.b); //@\sourceref{geometry/linesAndSegments.cpp}@
 }
 
 pair<int, int> intersect(vector<seg>& segs) {
diff --git a/content/geometry/spheres.cpp b/content/geometry/spheres.cpp
index ec22262..d34bca9 100644
--- a/content/geometry/spheres.cpp
+++ b/content/geometry/spheres.cpp
@@ -1,3 +1,16 @@
+// 3D Punkt in kartesischen Koordinaten.
+struct point{
+	double x, y, z;
+	point() {}
+	point(double x, double y, double z) : x(x), y(y), z(z) {}
+	point(double lat, double lon) {
+		lat *= PI / 180.0; lon *= PI / 180.0;
+		x = cos(lat) * sin(lon);
+		y = cos(lat) * cos(lon);
+		z = sin(lat);
+	}
+};
+
 // Great Circle Distance mit Längen- und Breitengrad.
 double gcDist(double pLat, double pLon,
 	          double qLat, double qLon, double radius) {
@@ -11,19 +24,6 @@ double gcDist(double pLat, double pLon,
 }
 
 // Great Circle Distance mit kartesischen Koordinaten.
-double gcDist(point p, point q) {
+double gcDist(point p, point q) { // radius = 1
 	return acos(p.x * q.x + p.y * q.y + p.z * q.z);
-}
-
-// 3D Punkt in kartesischen Koordinaten.
-struct point{
-	double x, y, z;
-	point() {}
-	point(double x, double y, double z) : x(x), y(y), z(z) {}
-	point(double lat, double lon) {
-		lat *= PI / 180.0; lon *= PI / 180.0;
-		x = cos(lat) * sin(lon);
-		y = cos(lat) * cos(lon);
-		z = sin(lat);
-	}
-};
+}
\ No newline at end of file
diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp
index 6470232..eee5082 100644
--- a/content/graph/bitonicTSP.cpp
+++ b/content/graph/bitonicTSP.cpp
@@ -27,5 +27,5 @@ auto bitonicTSP() {
 	(lt.back() == 1 ? lt : ut).push_back(0);
 	reverse(all(lt));
 	lt.insert(lt.end(), all(ut));
-	return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+	return lt; // Enthält Knoten 0 zweimal. An erster und letzter Position.
 }
diff --git a/content/graph/bitonicTSPsimple.cpp b/content/graph/bitonicTSPsimple.cpp
index 8b6e6c5..cacfb9c 100644
--- a/content/graph/bitonicTSPsimple.cpp
+++ b/content/graph/bitonicTSPsimple.cpp
@@ -23,5 +23,5 @@ auto bitonicTSP() {
 			rl.push_back(v); p2 = v;
 	}}
 	lr.insert(lr.end(), rl.rbegin(), rl.rend());
-	return lr;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+	return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position.
 }
diff --git a/content/graph/connect.cpp b/content/graph/connect.cpp
index ffcd6c2..7940b37 100644
--- a/content/graph/connect.cpp
+++ b/content/graph/connect.cpp
@@ -10,7 +10,7 @@ struct connect {
 	}
 
 	void addEdge(int u, int v, int id) {
-		lct.nodes[id + n] = LCT::Node(id + n, id + n);
+		lct.nodes[id + n] = LCT::Node(id + n, id);
 		edges[id] = {u, v};
 		if (connected(u, v)) {
 			int old = lct.query(&lct.nodes[u], &lct.nodes[v]);
diff --git a/content/graph/dinic.cpp b/content/graph/dinic.cpp
new file mode 100644
index 0000000..2e58a2d
--- /dev/null
+++ b/content/graph/dinic.cpp
@@ -0,0 +1,55 @@
+struct Edge {
+	int to, rev;
+	ll f, c;
+};
+
+vector<vector<Edge>> adj;
+int s, t;
+vector<int> pt, dist;
+
+void addEdge(int u, int v, ll c) {
+	adj[u].push_back({v, (int)sz(adj[v]), 0, c});
+	adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0});
+}
+
+bool bfs() {
+	dist.assign(sz(adj), -1);
+	dist[s] = 0;
+	queue<int> q({s});
+	while (!q.empty() && dist[t] < 0) {
+		int v = q.front(); q.pop();
+		for (Edge& e : adj[v]) {
+			if (dist[e.to] < 0 && e.c - e.f > 0) {
+				dist[e.to] = dist[v] + 1;
+				q.push(e.to);
+	}}}
+	return dist[t] >= 0;
+}
+
+ll dfs(int v, ll flow = INF) {
+	if (v == t || flow == 0) return flow;
+	for (; pt[v] < sz(adj[v]); pt[v]++) {
+		Edge& e = adj[v][pt[v]];
+		if (dist[e.to] != dist[v] + 1) continue;
+		ll cur = dfs(e.to, min(e.c - e.f, flow));
+		if (cur > 0) {
+			e.f += cur;
+			adj[e.to][e.rev].f -= cur;
+			return cur;
+	}}
+	return 0;
+}
+
+ll maxFlow(int source, int target) {
+	s = source, t = target;
+	ll flow = 0;
+	while (bfs()) {
+		pt.assign(sz(adj), 0);
+		ll cur;
+		do {
+			cur = dfs(s);
+			flow += cur;
+		} while (cur > 0);
+	}
+	return flow;
+}
diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp
index f4e833a..0974b78 100644
--- a/content/graph/dinicScaling.cpp
+++ b/content/graph/dinicScaling.cpp
@@ -26,17 +26,18 @@ bool bfs(ll lim) {
 	return dist[t] >= 0;
 }
 
-bool dfs(int v, ll flow) {
-	if (v == t) return true;
+ll dfs(int v, ll flow) {
+	if (v == t || flow == 0) return flow;
 	for (; pt[v] < sz(adj[v]); pt[v]++) {
 		Edge& e = adj[v][pt[v]];
 		if (dist[e.to] != dist[v] + 1) continue;
-		if (e.c - e.f >= flow && dfs(e.to, flow)) {
-			e.f += flow;
-			adj[e.to][e.rev].f -= flow;
-			return true;
+		ll cur = dfs(e.to, min(e.c - e.f, flow));
+		if (cur > 0) {
+			e.f += cur;
+			adj[e.to][e.rev].f -= cur;
+			return cur;
 	}}
-	return false;
+	return 0;
 }
 
 ll maxFlow(int source, int target) {
@@ -45,7 +46,11 @@ ll maxFlow(int source, int target) {
 	for (ll lim = (1LL << 62); lim >= 1; lim /= 2) {
 		while (bfs(lim)) {
 			pt.assign(sz(adj), 0);
-			while (dfs(s, lim)) flow += lim;
+			ll cur;
+			do {
+				cur = dfs(s, lim);
+				flow += cur;
+			} while (cur > 0);
 	}}
 	return flow;
 }
diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp
index 73a9eae..ec36026 100644
--- a/content/graph/pushRelabel.cpp
+++ b/content/graph/pushRelabel.cpp
@@ -29,7 +29,7 @@ ll maxFlow(int s, int t) {
 	cur.assign(n, 0);
 	H.assign(n, 0);
 	H[s] = n;
-	ec[t] = 1;//never set t to active...
+	ec[t] = 1; //never set t to active...
 	vector<int> co(2*n);
 	co[0] = n - 1;
 	for (Edge& e : adj[s]) addFlow(e, e.c);
diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp
index 4c6a748..379c839 100644
--- a/content/graph/reroot.cpp
+++ b/content/graph/reroot.cpp
@@ -1,62 +1,48 @@
-// Usual Tree DP can be broken down in 4 steps:
-// - Initialize dp[v] = identity
-// - Iterate over all children w and take a value for w 
-//	 by looking at dp[w] and possibly the edge label of v -> w
-// - combine the values of those children
-//	 usually this operation should be commutative and associative
-// - finalize the dp[v] after iterating over all children
+using W = ll; // edge weight type
+vector<vector<pair<int, W>>> adj;
+
 struct Reroot {
-	using T = ll;
+	using T = ll; // dp type
 
-	// identity element
-	T E() {}
-	// x: dp value of child
-	// e: index of edge going to child
-	T takeChild(T x, int e) {}
-	T comb(T x, T y) {}
-	// called after combining all dp values of children
-	T fin(T x, int v) {}
+	static constexpr T E = 0; // neutral element
+	T takeChild(int v, int c, W w, T x) {} // move child along edge
+	static T comb(T x, T y) {}
+	T fin(int v, T x) {} // add v to own dp value x
 
-	vector<vector<pair<int, int>>> g;
-	vector<int> ord, pae;
 	vector<T> dp;
 
-	T dfs(int v) {
-		ord.push_back(v);
-		for (auto [w, e] : g[v]) {
-			g[w].erase(find(all(g[w]), pair(v, e^1)));
-			pae[w] = e^1;
-			dp[v] = comb(dp[v], takeChild(dfs(w), e));
+	T dfs0(int v, int from = -1) {
+		T val = E;
+		for (auto [u, w] : adj[v]) {
+			if (u == from) continue;
+			val = comb(val, takeChild(v, u, w, dfs0(u, v)));
 		}
-		return dp[v] = fin(dp[v], v);
+		return dp[v] = fin(v, val);
 	}
 
-	vector<T> solve(int n, vector<pair<int, int>> edges) {
-		g.resize(n);
-		for (int i = 0; i < n-1; i++) {
-			g[edges[i].first].emplace_back(edges[i].second, 2*i);
-			g[edges[i].second].emplace_back(edges[i].first, 2*i+1);
+	void dfs1(int v, int from = -1) {
+		vector<T> pref = {E};
+		for (auto [u, w] : adj[v]) {
+			pref.push_back(takeChild(v, u, w, dp[u]));
 		}
-		pae.assign(n, -1);
-		dp.assign(n, E());
-		dfs(0);
-		vector<T> updp(n, E()), res(n, E());
-		for (int v : ord) {
-			vector<T> pref(sz(g[v])+1), suff(sz(g[v])+1);
-			if (v != 0) pref[0] = takeChild(updp[v], pae[v]);
-			for (int i = 0; i < sz(g[v]); i++){
-				auto [u, w] = g[v][i];
-				pref[i+1] = suff[i] = takeChild(dp[u], w);
-				pref[i+1] = comb(pref[i], pref[i+1]);
-			}
-			for (int i = sz(g[v])-1; i >= 0; i--) {
-				suff[i] = comb(suff[i], suff[i+1]);
-			}
-			for (int i = 0; i < sz(g[v]); i++) {
-				updp[g[v][i].first] = fin(comb(pref[i], suff[i+1]), v);
-			}
-			res[v] = fin(pref.back(), v);
+		auto suf = pref;
+		partial_sum(all(pref), pref.begin(), comb);
+		exclusive_scan(suf.rbegin(), suf.rend(),
+		               suf.rbegin(), E, comb);
+
+		for (int i = 0; i < sz(adj[v]); i++) {
+			auto [u, w] = adj[v][i];
+			if (u == from) continue;
+			dp[v] = fin(v, comb(pref[i], suf[i + 1]));
+			dfs1(u, v);
 		}
-		return res;
+		dp[v] = fin(v, suf[0]);
+	}
+
+	auto solve() {
+		dp.assign(sz(adj), E);
+		dfs0(0);
+		dfs1(0);
+		return dp;
 	}
 };
diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp
index ac9a40b..32f1099 100644
--- a/content/graph/scc.cpp
+++ b/content/graph/scc.cpp
@@ -1,11 +1,12 @@
-vector<vector<int>> adj, sccs;
-int counter;
+vector<vector<int>> adj;
+int counter, sccCounter;
 vector<bool> inStack;
 vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten.
 
 void visit(int v) {
 	int old = low[v] = counter++;
-	s.push_back(v); inStack[v] = true;
+	s.push_back(v);
+	inStack[v] = true;
 
 	for (auto u : adj[v]) {
 		if (low[u] < 0) visit(u);
@@ -13,20 +14,20 @@ void visit(int v) {
 	}
 
 	if (old == low[v]) {
-		sccs.push_back({});
+		sccCounter++;
 		for (int u = -1; u != v;) {
-			u = s.back(); s.pop_back(); inStack[u] = false;
-			idx[u] = sz(sccs) - 1;
-			sccs.back().push_back(u);
+			u = s.back();
+			s.pop_back();
+			inStack[u] = false;
+			idx[u] = sccCounter - 1;
 }}}
 
 void scc() {
 	inStack.assign(sz(adj), false);
 	low.assign(sz(adj), -1);
 	idx.assign(sz(adj), -1);
-	sccs.clear();
 
-	counter = 0;
+	counter = sccCounter = 0;
 	for (int i = 0; i < sz(adj); i++) {
 		if (low[i] < 0) visit(i);
 }}
diff --git a/content/graph/virtualTree.cpp b/content/graph/virtualTree.cpp
index 27d2d6c..6233b27 100644
--- a/content/graph/virtualTree.cpp
+++ b/content/graph/virtualTree.cpp
@@ -3,13 +3,13 @@ vector<int> in, out;
 
 void virtualTree(vector<int> ind) { // indices of used nodes
 	sort(all(ind), [&](int x, int y) {return in[x] < in[y];});
-	for (int i = 0, n = sz(ind); i < n - 1; i++) {
-		ind.push_back(lca(ind[i], ind[i + 1]));
+	for (int i = 1, n = sz(ind); i < n; i++) {
+		ind.push_back(lca(ind[i - 1], ind[i]));
 	}
 	sort(all(ind), [&](int x, int y) {return in[x] < in[y];});
 	ind.erase(unique(all(ind)), ind.end());
 
-	int n = ind.size();
+	int n = sz(ind);
 	vector<vector<int>> tree(n);
 	vector<int> st = {0};
 	for (int i = 1; i < n; i++) {
diff --git a/content/latexHeaders/layout.sty b/content/latexHeaders/layout.sty
index 096cf23..01915f3 100644
--- a/content/latexHeaders/layout.sty
+++ b/content/latexHeaders/layout.sty
@@ -10,9 +10,8 @@
 % Headline and bottomline.
 \usepackage{scrlayer-scrpage}
 \pagestyle{scrheadings}
-\clearscrheadfoot
-\ihead{\university}
-\chead{\teamname}
+\clearpairofpagestyles
+\ihead{\university{} -- \teamname{}}
 \ohead{\pagemark}
 
 % Shift the title up to waste less space.
@@ -43,7 +42,7 @@
 
 % use less space...
 %\usepackage[subtle, sections, indent, leading, charwidths]{savetrees}
-\usepackage[moderate,sections]{savetrees}
+\usepackage[moderate]{savetrees}
 \RedeclareSectionCommands[
 	beforeskip=1pt plus 5pt,
 	afterskip=0.1pt plus 1.5pt
diff --git a/content/latexHeaders/math.sty b/content/latexHeaders/math.sty
index c34cc99..d758f71 100644
--- a/content/latexHeaders/math.sty
+++ b/content/latexHeaders/math.sty
@@ -6,6 +6,7 @@
 \usepackage{mathtools}
 \usepackage{amssymb}
 \usepackage{ntheorem}
+\usepackage{nicefrac}
 
 %\usepackage{pxfonts}
 \usepackage[scaled=0.945,largesc,looser]{newpxtext}%better than pxfonts...
diff --git a/content/math/divSum.cpp b/content/math/divSum.cpp
new file mode 100644
index 0000000..48302b5
--- /dev/null
+++ b/content/math/divSum.cpp
@@ -0,0 +1,8 @@
+ll divSum(ll n, ll m, ll a, ll b){
+	if (m == 0) return 0;
+	ll ans = a/m * n*(n-1)/2 + b/m * n;
+	a %= m;
+	b %= m;
+	ll y = (a*(n-1)+b) / m;
+	return ans + y * (n-1) - divSum(y, a, m, m-b-1);
+}
diff --git a/content/math/gauss.cpp b/content/math/gauss.cpp
index 8129fd2..d431e52 100644
--- a/content/math/gauss.cpp
+++ b/content/math/gauss.cpp
@@ -14,19 +14,17 @@ void takeAll(int n, int line) {
 int gauss(int n) {
 	vector<bool> done(n, false);
 	for (int i = 0; i < n; i++) {
-		int swappee = i; // Sucht Pivotzeile für bessere Stabilität.
-		for (int j = 0; j < n; j++) {
-			if (done[j]) continue;
-			if (abs(mat[j][i]) > abs(mat[i][i])) swappee = j;
+		int j = i; // Sucht Pivotzeile für bessere Stabilität.
+		for (int k = 0; k < n; k++) {
+			if (!done[k] && abs(mat[k][i]) > abs(mat[i][i])) j = k;
 		}
-		swap(mat[i], mat[swappee]);
+		swap(mat[i], mat[j]);
 		if (abs(mat[i][i]) > EPS) {
 			normalLine(i);
 			takeAll(n, i);
 			done[i] = true;	
 	}}
-	// Ab jetzt nur checks bzgl. Eindeutigkeit/Existenz der Lösung.
-	for (int i = 0; i < n; i++) {
+	for (int i = 0; i < n; i++) { // gauss fertig, prüfe Lösung
 		bool allZero = true;
 		for (int j = i; j < n; j++) allZero &= abs(mat[i][j]) <= EPS;
 		if (allZero && abs(mat[i][n]) > EPS) return INCONSISTENT;
diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp
index 0241742..bf18c86 100644
--- a/content/math/lgsFp.cpp
+++ b/content/math/lgsFp.cpp
@@ -22,5 +22,4 @@ void gauss(int n, ll mod) {
 		normalLine(i, mod);
 		takeAll(n, i, mod);
 		done[i] = true;
-}}
-// für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@
+}} // für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@
diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp
index 2501e64..a8adacd 100644
--- a/content/math/linearRecurrence.cpp
+++ b/content/math/linearRecurrence.cpp
@@ -1,33 +1,30 @@
-constexpr ll mod = 1'000'000'007;
-vector<ll> modMul(const vector<ll>& a, const vector<ll>& b,
-                  const vector<ll>& c) {
-	ll n = sz(c);
-	vector<ll> res(n * 2 + 1);
-	for (int i = 0; i <= n; i++) { //a*b
-		for (int j = 0; j <= n; j++) {
-			res[i + j] += a[i] * b[j];
-			res[i + j] %= mod;
+constexpr ll mod = 998244353;
+// oder ntt mul @\sourceref{math/transforms/ntt.cpp}@
+vector<ll> mul(const vector<ll>& a, const vector<ll>& b) {
+	vector<ll> c(sz(a) + sz(b) - 1);
+	for (int i = 0; i < sz(a); i++) {
+		for (int j = 0; j < sz(b); j++) {
+			c[i+j] += a[i]*b[j] % mod;
 	}}
-	for (int i = 2 * n; i > n; i--) { //res%c
-		for (int j = 0; j < n; j++) {
-			res[i - 1 - j] += res[i] * c[j];
-			res[i - 1 - j] %= mod;
-	}}
-	res.resize(n + 1);
-	return res;
+	for (ll& x : c) x %= mod;
+	return c;
 }
 
 ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) {
-	assert(sz(f) == sz(c));
-	vector<ll> tmp(sz(c) + 1), a(sz(c) + 1);
-	tmp[0] = a[1] = 1; //tmp = (x^k) % c
-
-	for (k++; k > 0; k /= 2) {
-		if (k & 1) tmp = modMul(tmp, a, c);
-		a = modMul(a, a, c);
-	}
-
-	ll res = 0;
-	for (int i = 0; i < sz(c); i++) res += (tmp[i+1] * f[i]) % mod;
-	return res % mod;
+	int n = sz(c);
+	vector<ll> q(n + 1, 1);
+	for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i]) % mod;
+	vector<ll> p = mul(f, q);
+	p.resize(n);
+	p.push_back(0);
+	do {
+		vector<ll> q2 = q;
+		for (int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod;
+		vector<ll> x = mul(p, q2), y = mul(q, q2);
+		for (int i = 0; i <= n; i++){
+			p[i] = i == n ? 0 : x[2*i + (k&1)];
+			q[i] = y[2*i];
+		}
+	} while (k /= 2);
+	return p[0];
 }
diff --git a/content/math/linearRecurrenceOld.cpp b/content/math/linearRecurrenceOld.cpp
new file mode 100644
index 0000000..2501e64
--- /dev/null
+++ b/content/math/linearRecurrenceOld.cpp
@@ -0,0 +1,33 @@
+constexpr ll mod = 1'000'000'007;
+vector<ll> modMul(const vector<ll>& a, const vector<ll>& b,
+                  const vector<ll>& c) {
+	ll n = sz(c);
+	vector<ll> res(n * 2 + 1);
+	for (int i = 0; i <= n; i++) { //a*b
+		for (int j = 0; j <= n; j++) {
+			res[i + j] += a[i] * b[j];
+			res[i + j] %= mod;
+	}}
+	for (int i = 2 * n; i > n; i--) { //res%c
+		for (int j = 0; j < n; j++) {
+			res[i - 1 - j] += res[i] * c[j];
+			res[i - 1 - j] %= mod;
+	}}
+	res.resize(n + 1);
+	return res;
+}
+
+ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) {
+	assert(sz(f) == sz(c));
+	vector<ll> tmp(sz(c) + 1), a(sz(c) + 1);
+	tmp[0] = a[1] = 1; //tmp = (x^k) % c
+
+	for (k++; k > 0; k /= 2) {
+		if (k & 1) tmp = modMul(tmp, a, c);
+		a = modMul(a, a, c);
+	}
+
+	ll res = 0;
+	for (int i = 0; i < sz(c); i++) res += (tmp[i+1] * f[i]) % mod;
+	return res % mod;
+}
diff --git a/content/math/math.tex b/content/math/math.tex
index f670a70..644fbc8 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -109,8 +109,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/millerRabin.cpp}

 	\method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}}

 	\sourcecode{math/rho.cpp}

-	%\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}

-	%\sourcecode{math/squfof.cpp}

 \end{algorithm}

 

 \begin{algorithm}{Teiler}

@@ -138,8 +136,9 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	Sei $f(n)=c_{0}f(n-1)+c_{1}f(n-2)+\dots + c_{n-1}f(0)$ eine lineare Rekurrenz.

 	

 	\begin{methods}

-		\method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot n^2}

+		\method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot \text{mul}(n)}

 	\end{methods}

+	Die Polynom-Multiplikation kann auch mit NTT gemacht werden!

 	\sourcecode{math/linearRecurrence.cpp}

 	Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:

 	$$\renewcommand\arraystretch{1.5}

@@ -308,7 +307,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 \method{gauss}{löst LGS}{n^3}

 \sourcecode{math/gauss.cpp}

 

-\vfill\null\columnbreak

+\begin{algorithm}{Inversionszahl}

+	\vspace{-2pt}

+	\sourcecode{math/inversions.cpp}

+\end{algorithm}

 

 \begin{algorithm}{Numerisch Extremstelle bestimmen}

 	\sourcecode{math/goldenSectionSearch.cpp}

@@ -318,7 +320,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/simpson.cpp}

 \end{algorithm}

 

-

 \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}

 	Multipliziert Polynome $A$ und $B$.

 	\begin{itemize}

@@ -342,21 +343,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
     \sourcecode{math/transforms/seriesOperations.cpp}

 \end{algorithm}

 

-\begin{algorithm}{Inversionszahl}

-	\sourcecode{math/inversions.cpp}

-\end{algorithm}

-

-\subsection{Satz von \textsc{Sprague-Grundy}}

-Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:

-\[

-g\left(X\right) := \min\left\{

-\mathbb{Z}_0^+ \setminus

-\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}

-\right\}

-\]

-$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\

-Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.

-

 \subsection{Kombinatorik}

 

 \paragraph{\textsc{Wilson}'s Theorem}

@@ -389,7 +375,9 @@ so gilt
 %\begin{algorithm}{Binomialkoeffizienten}

 \paragraph{Binomialkoeffizienten}

 	Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.

-

+	

+	\input{math/tables/binom}

+	

 	\begin{methods}

 		\method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}}

 		\method{calc\_binom}{berechnet Binomialkoeffizient}{1}

@@ -498,7 +486,7 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
 \begin{align*}

 	p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\

 	p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[2pt]

-	p(n)&=\sum_{k=1}^{n} p_k(n)=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}p\bigg(n - \frac{k(3k-1)}{2}\bigg)

+	p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg]

 \end{align*}

 \begin{itemize}

 	\item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.

@@ -508,6 +496,59 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
 \subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}

 \input{math/tables/twelvefold}

 

+\subsection{Platonische Körper}

+\input{math/tables/platonic}

+

+\input{math/tables/probability}

+

+\subsection{Satz von \textsc{Sprague-Grundy}}

+Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:

+\[

+g\left(X\right) := \min\left\{

+\mathbb{Z}_0^+ \setminus

+\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}

+\right\}

+\]

+$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\

+Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.

+

+\subsection{Nim-Spiele}

+\begin{itemize}

+	\item[\ding{182}] letzter gewinnt (normal)

+	\item[\ding{183}] letzter verliert

+\end{itemize}

+\input{math/tables/nim}

+

+\subsection{Verschiedenes}

+\input{math/tables/stuff}

+

+\begin{algorithm}{Div Sum}

+	\method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m}  \right\rfloor$}{\log(n)}

+	\textbf{Wichtig:} $b$ darf nicht negativ sein!

+	\sourcecode{math/divSum.cpp}

+\end{algorithm}

+

+\begin{algorithm}{Min Mod}

+	\begin{methods}

+		\method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$,}{\log(m)}

+		\method{}{der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{}

+		\method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)}

+	\end{methods}

+	\textbf{Wichtig:} $0 \leq a, b, l, r < m$

+	\sourcecode{math/minMod.cpp}

+\end{algorithm}

+

+\subsection{Reihen}

+\input{math/tables/series}

+

+\subsection{Wichtige Zahlen}

+\input{math/tables/prime-composite}

+

+\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }

+\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}

+\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!

+\sourcecode{math/recover.cpp}

+

 \optional{

 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}

 \begin{methods}

@@ -516,9 +557,10 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
 	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}

 \end{methods}

 \sourcecode{math/piLehmer.cpp}

-}

 

-%\input{math/tables/numbers}

+\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}

+\sourcecode{math/piLegendre.cpp}

+}

 

 \begin{algorithm}[optional]{Big Integers}

 	\sourcecode{math/bigint.cpp}

diff --git a/content/math/minMod.cpp b/content/math/minMod.cpp
new file mode 100644
index 0000000..a80e783
--- /dev/null
+++ b/content/math/minMod.cpp
@@ -0,0 +1,22 @@
+ll firstVal(ll a, ll m, ll l, ll r) {
+	if (l == 0) return 0;
+	if (a == 0) return -1;
+	if ((l-1)/a < r/a) return (l+a-1) / a*a;
+	ll s = (r+a-1) / a*a;
+	ll v = firstVal(m % a, a, s-r, s-l);
+	return v < 0 ? -1 : s - v;
+}
+
+ll minMod(ll n, ll m, ll a, ll b) {
+	if (a == 0) return b;
+	ll g = gcd(m, a);
+	ll c = b % g;
+	m /= g;
+	a /= g;
+	b /= g;
+	ll ai = multInv(a, m);
+	ll l = ai*b % m;
+	ll r = (n-1 + ai*b) % m;
+	if (n >= m || l > r) return c;
+	return a * firstVal(ai, m, l, r) % m * g + c;
+}
\ No newline at end of file
diff --git a/content/math/polynomial.cpp b/content/math/polynomial.cpp
index 44f6207..84f3aaa 100644
--- a/content/math/polynomial.cpp
+++ b/content/math/polynomial.cpp
@@ -1,7 +1,7 @@
 struct poly {
 	vector<ll> data;
 
-	poly(int deg = 0) : data(max(1, deg)) {}
+	poly(int deg = 0) : data(1 + deg) {}
 	poly(initializer_list<ll> _data) : data(_data) {}
 
 	int size() const {return sz(data);}
@@ -40,17 +40,18 @@ struct poly {
 
 	//return p(x+a)
 	poly operator<<(ll a) const {
-		poly res(size());
+		poly res(size() - 1);
 		for (int i = size() - 1; i >= 0; i--) {
 			for (int j = size() - i - 1; j >= 1; j--)
 				res[j] = (res[j] * a + res[j - 1]) % mod;
-			res[0] = (res[0] * a + res[i]) % mod;
+			res[0] = (res[0] * a + data[i]) % mod;
 		}
 		return res;
 	}
 
 	pair<poly, poly> divmod(const poly& d) const {
 		int i = size() - d.size();
+		if (i <= 0) return {{}, *this};
 		poly s(i + 1), r = *this;
 		ll inv = multInv(d.data.back(), mod);
 		for (; i >= 0; i--) {
diff --git a/content/math/recover.cpp b/content/math/recover.cpp
new file mode 100644
index 0000000..1a593f0
--- /dev/null
+++ b/content/math/recover.cpp
@@ -0,0 +1,13 @@
+ll sq(ll x) {return x*x;}
+
+array<ll, 2> recover(ll c, ll m) {
+	array<ll, 2> u = {m, 0}, v = {c, 1};
+	while (m <= 2 * sq(v[0])) {
+		ll q = u[0] / v[0];
+		u[0] -= q * v[0];
+		u[1] -= q * v[1];
+		swap(u, v);
+	}
+	if (v[1] <= 0 || 2 * sq(v[1]) >= m) return {-1, -1};
+	return v;
+}
diff --git a/content/math/shortModInv.cpp b/content/math/shortModInv.cpp
index f696cce..cf91ca0 100644
--- a/content/math/shortModInv.cpp
+++ b/content/math/shortModInv.cpp
@@ -1,3 +1,3 @@
 ll multInv(ll x, ll m) { // x^{-1} mod m
-    return 1 < x ? m - multInv(m % x, x) * m / x : 1;
+	return 1 < x ? m - multInv(m % x, x) * m / x : 1;
 }
diff --git a/content/math/squfof.cpp b/content/math/squfof.cpp
deleted file mode 100644
index 1cb97de..0000000
--- a/content/math/squfof.cpp
+++ /dev/null
@@ -1,89 +0,0 @@
-using lll = __int128;

-

-constexpr lll multipliers[] = {1, 3, 5, 7,

-                               11, 3*5, 3*7, 3*11,

-                               5*7, 5*11, 7*11,

-                               3*5*7, 3*5*11, 3*7*11,

-                               5*7*11, 3*5*7*11};

-

-lll root(lll x) {

-	lll r = sqrtl(x);

-	while(r*r < x) r++;

-	while(r*r > x) r--;

-	return r;

-}

-

-lll croot(lll x) {

-	lll r = cbrtl(x);

-	while(r*r*r < x) r++;

-	while(r*r*r > x) r--;

-	return r;

-}

-

-lll squfof(lll N) {

-	lll s = croot(N);

-	if (s*s*s == N) return s;

-	s = root(N);

-	if (s*s == N) return s;

-	for (lll k : multipliers) {

-		lll D = k * N;

-		lll Po, P, Pprev, q, b, r, i;

-		Po = Pprev = P = root(D);

-		lll Qprev = 1;

-		lll Q = D - Po*Po;

-		lll L = 2 * root(2 * s);

-		lll B = 3 * L;

-		for (i = 2; i < B; i++) {

-			b = (Po + P) / Q;

-			P = b*Q - P;

-			q = Q;

-			Q = Qprev + b * (Pprev - P);

-			r = root(Q);

-			if (!(i & 1) && r*r == Q) break;

-			Qprev = q;

-			Pprev = P;

-		}

-		if (i >= B) continue;

-		b = (Po - P) / r;

-		Pprev = P = b*r + P;

-		Qprev = r;

-		Q = (D-Pprev*Pprev)/Qprev;

-		i = 0;

-		do {

-			b = (Po + P) / Q;

-			Pprev = P;

-			P = b*Q - P;

-			q = Q;

-			Q = Qprev +	b * (Pprev - P);

-			Qprev = q;

-			i++;

-		} while(P != Pprev);

-		r = gcd(N, Qprev);

-		if (r != 1 && r != N) return r;

-	}

-	exit(1);//try fallback to pollard rho

-}

-

-constexpr lll trialLim = 5'000;

-

-void factor(lll n, map<lll, int>& facts) {

-	for (lll i = 2; i * i <= n && i <= trialLim; i++) {

-		while (n % i == 0) {

-			facts[i]++;

-			n /= i;

-	}}

-	if (n > 1 && n < trialLim * trialLim) {

-		facts[n]++;

-	} else {

-		vector<lll> todo = {n};

-		while (!todo.empty()) {

-			lll c = todo.back();

-			todo.pop_back();

-			if (c == 1) continue;

-			if (isPrime(c)) {

-				facts[c]++;

-			} else {

-				lll d = squfof(c);

-				todo.push_back(d);

-				todo.push_back(c / d);

-}}}}

diff --git a/content/math/tables.tex b/content/math/tables.tex
deleted file mode 100644
index c422d73..0000000
--- a/content/math/tables.tex
+++ /dev/null
@@ -1,22 +0,0 @@
-\enlargethispage{0.2cm}
-\begin{multicols*}{2}
-	\refstepcounter{subsection}
-	\subsectionmark{Tables}
-	\addcontentsline{toc}{subsection}{\protect\numberline{\thesubsection}Tables}
-
-	\input{math/tables/binom}
-	\vfill
-	\input{math/tables/prime-composite}
-	\vfill
-	\input{math/tables/platonic}
-	\vfill
-	\input{math/tables/series}
-
-	\columnbreak
-
-	\input{math/tables/probability}
-	\vfill
-	\input{math/tables/stuff}
-	\vfill
-	\input{math/tables/nim}
-\end{multicols*}
diff --git a/content/math/tables/binom.tex b/content/math/tables/binom.tex
index 878a6b0..9fc9ae3 100644
--- a/content/math/tables/binom.tex
+++ b/content/math/tables/binom.tex
@@ -1,28 +1,27 @@
-\begin{tabularx}{\linewidth}{|XXXX|}
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|C|}
 	\hline
-	\multicolumn{4}{|c|}{Binomialkoeffizienten} \\
-	\hline
-	\multicolumn{4}{|c|}{
 	$\frac{n!}{k!(n - k)!} \hfill=\hfill
 	\binom{n}{k} \hfill=\hfill
 	\binom{n}{n - k} \hfill=\hfill
 	\frac{n}{k}\binom{n - 1}{k - 1} \hfill=\hfill
 	\frac{n-k+1}{k}\binom{n}{k - 1} \hfill=\hfill
-	\binom{n - 1}{k} + \binom{n - 1}{k - 1} \hfill=\hfill
+	\frac{k+1}{n-k}\binom{n}{k + 1} \hfill=\hfill$\\
+	
+	$\binom{n - 1}{k - 1} + \binom{n - 1}{k} \hfill=\hfill
+	\binom{n + 1}{k + 1} - \binom{n}{k + 1} \hfill=\hfill
 	(-1)^k \binom{k - n - 1}{k} \hfill\approx\hfill
-	2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$
-	} \\
+	2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$\\
 	\grayhline
 	
-	$\sum\limits_{k = 0}^n \binom{n}{k} = 2^n$ &
-	$\sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}$ &
-	$\sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}$ &
-	$\sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\
+	$\sum\limits_{k = 0}^n \binom{n}{k} = 2^n\hfill
+	\sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}\hfill
+	\sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}\hfill
+	\sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\
 	
-	$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}$ &
-	$\sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}$ &
-	\multicolumn{2}{l|}{
-	$\sum\limits_{i = 1}^n \binom{n}{i} F_i = F_{2n} \quad F_n = n\text{-th Fib.}$
-	}\\
+	$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}\hfill
+	\sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}\hfill
+	\sum\limits_{i = 1}^n \binom{n}{i} \mathit{Fib}_i = \mathit{Fib}_{2n}$\\
 	\hline
 \end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/nim.tex b/content/math/tables/nim.tex
index 8490d42..66e289e 100644
--- a/content/math/tables/nim.tex
+++ b/content/math/tables/nim.tex
@@ -1,7 +1,6 @@
+\begin{expandtable}
 \begin{tabularx}{\linewidth}{|p{0.37\linewidth}|X|}
 	\hline
-	\multicolumn{2}{|c|}{Nim-Spiele (\ding{182} letzter gewinnt (normal), \ding{183} letzter verliert)} \\
-	\hline
 	Beschreibung &
 	Strategie \\
 	\hline
@@ -94,3 +93,5 @@
 	Periode ab $n = 72$ der Länge $12$.\\
 	\hline
 \end{tabularx}
+\end{expandtable}
+	
\ No newline at end of file
diff --git a/content/math/tables/numbers.tex b/content/math/tables/numbers.tex
deleted file mode 100644
index 1dc9f38..0000000
--- a/content/math/tables/numbers.tex
+++ /dev/null
@@ -1,59 +0,0 @@
-\begin{expandtable}
-\begin{tabularx}{\linewidth}{|l|X|}
-	\hline
-	\multicolumn{2}{|c|}{Berühmte Zahlen} \\
-	\hline
-	\textsc{Fibonacci}	&
-	$f(0) = 0 \quad
-	f(1) = 1 \quad
-	f(n+2) = f(n+1) + f(n)$ \\
-	\grayhline
-	
-	\textsc{Catalan}	&
-	$C_0 = 1 \qquad
-	C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =
-	\frac{1}{n + 1}\binom{2n}{n} = \frac{2(2n - 1)}{n+1} \cdot C_{n-1}$ \\
-	\grayhline
-	
-	\textsc{Euler} I &
-	$\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \qquad
-	\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1} $ \\
-	\grayhline
-	
-	\textsc{Euler} II &
-	$\eulerII{n}{0} = 1 \quad
-	\eulerII{n}{n} = 0 \quad$\\
-	& $\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}$ \\
-	\grayhline
-	
-	\textsc{Stirling} I &
-	$\stirlingI{0}{0} = 1 \qquad
-	\stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad
-	\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}$ \\
-	\grayhline
-	
-	\textsc{Stirling} II &
-	$\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
-	\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} =
-	\frac{1}{k!} \sum\limits_{j=0}^{k} (-1)^{k-j}\binom{k}{j}j^n$\\
-	\grayhline
-	
-	\textsc{Bell} &
-	$B_1 = 1 \qquad
-	B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k}
-	= \sum\limits_{k = 0}^{n}\stirlingII{n}{k}$\\
-	\grayhline
-	
-	\textsc{Partitions} &
-	$p(0,0) = 1 \quad
-	p(n,k) = 0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0$ \\
-	& $p(n,k) = p(n-k,k) + p(n-1,k-1)$\\
-	\grayhline
-	
-	\textsc{Partitions} &
-	$f(0) = 1 \quad f(n) = 0~(n < 0)$ \\
-	& $f(n)=\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k+1)}{2})+\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k-1)}{2})$\\
-	
-	\hline
-\end{tabularx}
-\end{expandtable}
diff --git a/content/math/tables/platonic.tex b/content/math/tables/platonic.tex
index f4ee554..2866ccf 100644
--- a/content/math/tables/platonic.tex
+++ b/content/math/tables/platonic.tex
@@ -1,39 +1,39 @@
+\begin{expandtable}
 \begin{tabularx}{\linewidth}{|X|CCCX|}
 	\hline
-	\multicolumn{5}{|c|}{Platonische Körper} \\
-	\hline
-	Übersicht       & Seiten & Ecken & Kanten & dual zu \\
+	Übersicht       & |F|    & |V|   & |E|    & dual zu \\
 	\hline
 	Tetraeder       & 4      & 4     & 6      & Tetraeder \\
-	Würfel/Hexaeder & 6      & 8     & 12     & Oktaeder \\
-	Oktaeder        & 8      & 6     & 12     & Würfel/Hexaeder\\
+	Würfel          & 6      & 8     & 12     & Oktaeder \\
+	Oktaeder        & 8      & 6     & 12     & Würfel\\
 	Dodekaeder      & 12     & 20    & 30     & Ikosaeder \\
 	Ikosaeder       & 20     & 12    & 30     & Dodekaeder \\
 	\hline
 	\multicolumn{5}{|c|}{Färbungen mit maximal $n$ Farben (bis auf Isomorphie)} \\
 	\hline
-	\multicolumn{3}{|l}{Ecken vom Oktaeder/Seiten vom Würfel} &
+	\multicolumn{3}{|l}{|V| vom Oktaeder/|F| vom Würfel} &
 	\multicolumn{2}{l|}{$(n^6 + 3n^4 + 12n^3 + 8n^2)/24$} \\
 
-	\multicolumn{3}{|l}{Ecken vom Würfel/Seiten vom Oktaeder} &
+	\multicolumn{3}{|l}{|V| vom Würfel/|F| vom Oktaeder} &
 	\multicolumn{2}{l|}{$(n^8 + 17n^4 + 6n^2)/24$} \\
 
-	\multicolumn{3}{|l}{Kanten vom Würfel/Oktaeder} &
+	\multicolumn{3}{|l}{|E| vom Würfel/Oktaeder} &
 	\multicolumn{2}{l|}{$(n^{12} + 6n^7 + 3n^6 + 8n^4 + 6n^3)/24$} \\
 
-	\multicolumn{3}{|l}{Ecken/Seiten vom Tetraeder} &
+	\multicolumn{3}{|l}{|V|/|F| vom Tetraeder} &
 	\multicolumn{2}{l|}{$(n^4 + 11n^2)/12$} \\
 
-	\multicolumn{3}{|l}{Kanten vom Tetraeder} &
+	\multicolumn{3}{|l}{|E| vom Tetraeder} &
 	\multicolumn{2}{l|}{$(n^6 + 3n^4 + 8n^2)/12$} \\
 
-	\multicolumn{3}{|l}{Ecken vom Ikosaeder/Seiten vom Dodekaeder} &
+	\multicolumn{3}{|l}{|V| vom Ikosaeder/|F| vom Dodekaeder} &
 	\multicolumn{2}{l|}{$(n^{12} + 15n^6 + 44n^4)/60$} \\
 
-	\multicolumn{3}{|l}{Ecken vom Dodekaeder/Seiten vom Ikosaeder} &
+	\multicolumn{3}{|l}{|V| vom Dodekaeder/|F| vom Ikosaeder} &
 	\multicolumn{2}{l|}{$(n^{20} + 15n^{10} + 20n^8 + 24n^4)/60$} \\
 
-	\multicolumn{3}{|l}{Kanten vom Dodekaeder/Ikosaeder (evtl. falsch)} &
+	\multicolumn{3}{|l}{|E| vom Dodekaeder/Ikosaeder} &
 	\multicolumn{2}{l|}{$(n^{30} + 15n^{16} + 20n^{10} + 24n^6)/60$} \\
 	\hline
 \end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/prime-composite.tex b/content/math/tables/prime-composite.tex
index 99b3348..073b4ba 100644
--- a/content/math/tables/prime-composite.tex
+++ b/content/math/tables/prime-composite.tex
@@ -1,26 +1,31 @@
-\begin{tabularx}{\linewidth}{|r|r|rIr|rIrIr|C|}
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|r|rIr|rIr|r|r|}
 	\hline
-	\multicolumn{8}{|c|}{Important Numbers} \\
+	\multirow{2}{*}{$10^x$}
+	       & \multirow{2}{*}{Highly Composite}
+	                                      & \multirow{2}{*}{\# Divs}
+	                                                 & \multicolumn{2}{|c|}{Prime}
+	                                                                         &  \multirow{2}{*}{\# Primes} & \multirow{2}{*}{Primorial} \\
+	       &                              &          &       $<$ &       $>$ &                             &           \\
 	\hline
-	$10^x$ &             Highly Composite &  \# Divs & $<$ Prime & $>$ Prime &                   \# Primes & primorial & \\
-	\hline
-	     1 &                            6 &        4 &      $-3$ &      $+1$ &                           4 &         2 & \\
-	     2 &                           60 &       12 &      $-3$ &      $+1$ &                          25 &         3 & \\
-	     3 &                          840 &       32 &      $-3$ &      $+9$ &                         168 &         4 & \\
-	     4 &                       7\,560 &       64 &     $-27$ &      $+7$ &                      1\,229 &         5 & \\
-	     5 &                      83\,160 &      128 &      $-9$ &      $+3$ &                      9\,592 &         6 & \\
-	     6 &                     720\,720 &      240 &     $-17$ &      $+3$ &                     78\,498 &         7 & \\
-	     7 &                  8\,648\,640 &      448 &      $-9$ &     $+19$ &                    664\,579 &         8 & \\
-	     8 &                 73\,513\,440 &      768 &     $-11$ &      $+7$ &                 5\,761\,455 &         8 & \\
-	     9 &                735\,134\,400 &   1\,344 &     $-63$ &      $+7$ &                50\,847\,534 &         9 & \\
-	    10 &             6\,983\,776\,800 &   2\,304 &     $-33$ &     $+19$ &               455\,052\,511 &        10 & \\
-	    11 &            97\,772\,875\,200 &   4\,032 &     $-23$ &      $+3$ &            4\,118\,054\,813 &        10 & \\
-	    12 &           963\,761\,198\,400 &   6\,720 &     $-11$ &     $+39$ &           37\,607\,912\,018 &        11 & \\
-	    13 &        9\,316\,358\,251\,200 &  10\,752 &     $-29$ &     $+37$ &          346\,065\,536\,839 &        12 & \\
-	    14 &       97\,821\,761\,637\,600 &  17\,280 &     $-27$ &     $+31$ &       3\,204\,941\,750\,802 &        12 & \\
-	    15 &      866\,421\,317\,361\,600 &  26\,880 &     $-11$ &     $+37$ &      29\,844\,570\,422\,669 &        13 & \\
-	    16 &   8\,086\,598\,962\,041\,600 &  41\,472 &     $-63$ &     $+61$ &     279\,238\,341\,033\,925 &        13 & \\
-	    17 &  74\,801\,040\,398\,884\,800 &  64\,512 &      $-3$ &      $+3$ &  2\,623\,557\,157\,654\,233 &        14 & \\
-	    18 & 897\,612\,484\,786\,617\,600 & 103\,680 &     $-11$ &      $+3$ & 24\,739\,954\,287\,740\,860 &        16 & \\
+	     1 &                            6 &        4 &      $-3$ &      $+1$ &                           4 &         2 \\
+	     2 &                           60 &       12 &      $-3$ &      $+1$ &                          25 &         3 \\
+	     3 &                          840 &       32 &      $-3$ &      $+9$ &                         168 &         4 \\
+	     4 &                       7\,560 &       64 &     $-27$ &      $+7$ &                      1\,229 &         5 \\
+	     5 &                      83\,160 &      128 &      $-9$ &      $+3$ &                      9\,592 &         6 \\
+	     6 &                     720\,720 &      240 &     $-17$ &      $+3$ &                     78\,498 &         7 \\
+	     7 &                  8\,648\,640 &      448 &      $-9$ &     $+19$ &                    664\,579 &         8 \\
+	     8 &                 73\,513\,440 &      768 &     $-11$ &      $+7$ &                 5\,761\,455 &         8 \\
+	     9 &                735\,134\,400 &   1\,344 &     $-63$ &      $+7$ &                50\,847\,534 &         9 \\
+	    10 &             6\,983\,776\,800 &   2\,304 &     $-33$ &     $+19$ &               455\,052\,511 &        10 \\
+	    11 &            97\,772\,875\,200 &   4\,032 &     $-23$ &      $+3$ &            4\,118\,054\,813 &        10 \\
+	    12 &           963\,761\,198\,400 &   6\,720 &     $-11$ &     $+39$ &           37\,607\,912\,018 &        11 \\
+	    13 &        9\,316\,358\,251\,200 &  10\,752 &     $-29$ &     $+37$ &          346\,065\,536\,839 &        12 \\
+	    14 &       97\,821\,761\,637\,600 &  17\,280 &     $-27$ &     $+31$ &       3\,204\,941\,750\,802 &        12 \\
+	    15 &      866\,421\,317\,361\,600 &  26\,880 &     $-11$ &     $+37$ &      29\,844\,570\,422\,669 &        13 \\
+	    16 &   8\,086\,598\,962\,041\,600 &  41\,472 &     $-63$ &     $+61$ &     279\,238\,341\,033\,925 &        13 \\
+	    17 &  74\,801\,040\,398\,884\,800 &  64\,512 &      $-3$ &      $+3$ &  2\,623\,557\,157\,654\,233 &        14 \\
+	    18 & 897\,612\,484\,786\,617\,600 & 103\,680 &     $-11$ &      $+3$ & 24\,739\,954\,287\,740\,860 &        16 \\
 	\hline
 \end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/probability.tex b/content/math/tables/probability.tex
index f265d10..29f92e1 100644
--- a/content/math/tables/probability.tex
+++ b/content/math/tables/probability.tex
@@ -1,19 +1,15 @@
-\begin{tabularx}{\linewidth}{|LICIR|}
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|LIR|}
 	\hline
-	\multicolumn{3}{|c|}{
+	\multicolumn{2}{|c|}{
 		Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen)
 	} \\
 	\hline
-	$\E(X + Y) = \E(X) + \E(Y)$ &
-	$\E(\alpha X) = \alpha \E(X)$ &
-	$X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$\\
-	
-	$\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ &
-	$A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ &
-	$\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\
+	$\E(X + Y) = \E(X) + \E(Y)$                                & $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ \\
+	$\E(\alpha X) = \alpha \E(X)$                              & $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\
+	$X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$ & $A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$\\
 	\hline
 \end{tabularx}
-\vfill
 \begin{tabularx}{\linewidth}{|Xlr|lrX|}
 	\hline
 	\multicolumn{6}{|c|}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\
@@ -25,3 +21,4 @@
 	$\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ & \\
 	\hline
 \end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/series.tex b/content/math/tables/series.tex
index 3042781..9618c2b 100644
--- a/content/math/tables/series.tex
+++ b/content/math/tables/series.tex
@@ -1,33 +1,33 @@
-\begin{tabularx}{\linewidth}{|XIXIXIX|}
-	\hline
-	\multicolumn{4}{|c|}{Reihen} \\
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|XIXIX|}
 	\hline
 	$\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ &
 	$\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(2n + 1)}{6}$ &
-	$\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ &
-	$H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\
+	$\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ \\
 	\grayhline
 	
-	$\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \quad c \neq 1$ &	
-	$\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \quad \vert c \vert < 1$ &
-	$\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \quad \vert c \vert < 1$ &	
-	$\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \quad \vert c \vert < 1$ \\
+	$\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \hfill c \neq 1$ &	
+	$\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \hfill \vert c \vert < 1$ &
+	$\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \hfill \vert c \vert < 1$ \\
 	\grayhline
-	
+		
 	\multicolumn{2}{|lI}{
 		$\sum\limits_{i = 0}^n ic^i = \frac{nc^{n + 2} - (n + 1)c^{n + 1} + c}{(c - 1)^2} \quad c \neq 1$
 	} &	
-	\multicolumn{2}{l|}{
+	$\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \hfill \vert c \vert < 1$ \\
+	\grayhline	
+	
+	\multicolumn{2}{|lI}{
 		$\sum\limits_{i = 1}^n iH_i = \frac{n(n + 1)}{2}H_n - \frac{n(n - 1)}{4}$
-	} \\
+	} &
+	$H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\
 	\grayhline
 	
 	\multicolumn{2}{|lI}{
-		$\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$
-	} &
-	\multicolumn{2}{l|}{
 		$\sum\limits_{i = 1}^n \binom{i}{m}H_i =
 		\binom{n + 1}{m + 1} \left(H_{n + 1} - \frac{1}{m  + 1}\right)$
-	} \\
+	} &
+	$\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ \\
 	\hline
 \end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/stuff.tex b/content/math/tables/stuff.tex
index 3cf8b4c..82f2d3f 100644
--- a/content/math/tables/stuff.tex
+++ b/content/math/tables/stuff.tex
@@ -1,6 +1,7 @@
-\begin{tabularx}{\linewidth}{|ll|}
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|Ll|}
 	\hline
-	\multicolumn{2}{|C|}{Verschiedenes} \\
+	\multicolumn{2}{|c|}{Verschiedenes} \\
 	\hline
 	Türme von Hanoi, minimale Schirttzahl: &
 	$T_n = 2^n - 1$ \\
@@ -20,7 +21,7 @@
 	\#Wälder mit $k$ gewurzelten Bäumen	&
 	$\frac{k}{n}\binom{n}{k}n^{n-k}$ \\
 
-	\#Wälder mit $k$ gewurzelten Bäumen mit vorgegebenen Wurzelknoten&
+	\#Wälder mit $k$ gewurzelten~Bäumen mit vorgegebenen Wurzelknoten&
 	$\frac{k}{n}n^{n-k}$ \\
 
 	Derangements &
@@ -29,4 +30,4 @@
 	$\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\
 	\hline
 \end{tabularx}
-
+\end{expandtable}
diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp
index 4743674..b405698 100644
--- a/content/math/transforms/seriesOperations.cpp
+++ b/content/math/transforms/seriesOperations.cpp
@@ -4,7 +4,7 @@ vector<ll> poly_inv(const vector<ll>& a, int n) {
 		vector<ll> a2 = a, q2 = q;
 		a2.resize(2*len), q2.resize(2*len);
 		ntt(q2);
-		for (int j : {0, 1}) {
+		for (int _ : {0, 1}) {
 			ntt(a2);
 			for (int i = 0; i < 2*len; i++) a2[i] = a2[i]*q2[i] % mod;
 			ntt(a2, true);
@@ -24,10 +24,13 @@ vector<ll> poly_deriv(vector<ll> a) {
 }
 
 vector<ll> poly_integr(vector<ll> a) {
-	if (a.empty()) return {0};
-	a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod);
-	for (int i = sz(a)-2; i > 0; i--)
-		a[i] = a[i-1] * powMod(i, mod-2, mod) % mod;
+	static vector<ll> inv = {0, 1};
+	for (static int i = 2; i <= sz(a); i++)
+		inv.push_back(mod - mod / i * inv[mod % i] % mod);
+
+	a.push_back(0);
+	for (int i = sz(a) - 1; i > 0; i--)
+		a[i] = a[i-1] * inv[i] % mod;
 	a[0] = 0;
 	return a;
 }
@@ -35,8 +38,7 @@ vector<ll> poly_integr(vector<ll> a) {
 vector<ll> poly_log(vector<ll> a, int n) {
 	a = mul(poly_deriv(a), poly_inv(a, n));
 	a.resize(n-1);
-	a = poly_integr(a);
-	return a;
+	return poly_integr(a);
 }
 
 vector<ll> poly_exp(vector<ll> a, int n) {
diff --git a/content/other/bitOps.cpp b/content/other/bitOps.cpp
index 8079305..6230c86 100644
--- a/content/other/bitOps.cpp
+++ b/content/other/bitOps.cpp
@@ -3,13 +3,6 @@
 for (int subset = bitmask; subset > 0;
      subset = (subset - 1) & bitmask)
 
-// Zählt Anzahl der gesetzten Bits.
-int numberOfSetBits(int i) {
-	i = i - ((i >> 1) & 0x5555'5555);
-	i = (i & 0x3333'3333) + ((i >> 2) & 0x3333'3333);
-	return (((i + (i >> 4)) & 0x0F0F'0F0F) * 0x0101'0101) >> 24;
-}
-
 // Nächste Permutation in Bitmaske
 // (z.B. 00111 => 01011 => 01101 => ...)
 ll nextPerm(ll v) {
diff --git a/content/other/divideAndConquer.cpp b/content/other/divideAndConquer.cpp
index 830dc7f..9bd5f0c 100644
--- a/content/other/divideAndConquer.cpp
+++ b/content/other/divideAndConquer.cpp
@@ -5,7 +5,7 @@ void rec(int i, int j0, int j1, int m0, int m1) {
 	if (j1 < j0) return;
 	int jmid = (j0 + j1) / 2;
 
-	dp[i][jmid] = inf;
+	dp[i][jmid] = INF;
 	int bestk = m0;
 	for (int k = m0; k < min(jmid, m1 + 1); ++k) {
 		if (dp[i - 1][k] + C[k + 1][jmid] < dp[i][jmid]) {
@@ -18,7 +18,7 @@ void rec(int i, int j0, int j1, int m0, int m1) {
 }
 
 ll calc(int n, int m) {
-	dp = vector<vector<ll>>(m, vector<ll>(n, inf));
+	dp = vector<vector<ll>>(m, vector<ll>(n, INF));
 	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
 	for (int i = 1; i < m; i++) {
 		rec(i, 0, n - 1, 0, n - 1);
diff --git a/content/other/fastSubsetSum.cpp b/content/other/fastSubsetSum.cpp
new file mode 100644
index 0000000..84396f6
--- /dev/null
+++ b/content/other/fastSubsetSum.cpp
@@ -0,0 +1,21 @@
+int fastSubsetSum(vector<int> w, int t){
+	int a = 0, b = 0;
+	while(b < sz(w) && a + w[b] <= t) a += w[b++];
+	if(b == sz(w)) return a;
+	int m = *max_element(all(w));
+	vector<int> dp(2*m, -1), old;
+	dp[m+a-t] = b;
+	for(int i = b; i < sz(w); i++){
+		old = dp;
+		for(int j = 0; j < m; j++){
+			dp[j+w[i]] = max(dp[j+w[i]], old[j]);
+		}
+		for(int j = 2*m-1; j > m; j--){
+			for(int k = max(old[j], 0); k < dp[j]; k++){
+				dp[j-w[k]] = max(dp[j-w[k]], k);
+			}
+		}
+	}
+	for(a = t; dp[m+a-t] < 0; a--);
+	return a;
+}
\ No newline at end of file
diff --git a/content/other/josephus2.cpp b/content/other/josephus2.cpp
index 5086e13..33544ea 100644
--- a/content/other/josephus2.cpp
+++ b/content/other/josephus2.cpp
@@ -1,8 +1,5 @@
 int rotateLeft(int n) { // Der letzte Überlebende, 1-basiert.
-	for (int i = 31; i >= 0; i--) {
-		if (n & (1 << i)) {
-			n &= ~(1 << i);
-			break;
-	}}
-	n <<= 1; n++; return n;
+	int bits = __lg(n);
+	n ^= 1 << bits;
+	return 2 * n + 1;
 }
diff --git a/content/other/knuth.cpp b/content/other/knuth.cpp
index 1d513c8..aa54924 100644
--- a/content/other/knuth.cpp
+++ b/content/other/knuth.cpp
@@ -1,5 +1,5 @@
 ll calc(int n, int m, const vector<vector<ll>>& C) {
-	vector<vector<ll>> dp(m, vector<ll>(n, inf));
+	vector<vector<ll>> dp(m, vector<ll>(n, INF));
 	vector<vector<int>> opt(m, vector<int>(n + 1, n - 1));
 
 	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
diff --git a/content/other/other.tex b/content/other/other.tex
index 7a3c52b..59b5790 100644
--- a/content/other/other.tex
+++ b/content/other/other.tex
@@ -13,6 +13,19 @@
 	\sourcecode{other/timed.cpp}

 \end{algorithm}

 

+\begin{algorithm}{Overflow-sichere arithmetische Operationen}

+	Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.

+	\begin{expandtable}

+		\begin{tabularx}{\linewidth}{|lR|}

+			\hline

+			Addition & \code{__builtin_saddll_overflow(a, b, \&c)} \\

+			Subtraktion & \code{__builtin_ssubll_overflow(a, b, \&c)} \\

+			Multiplikation & \code{__builtin_smulll_overflow(a, b, \&c)} \\

+			\hline

+		\end{tabularx}

+	\end{expandtable}

+\end{algorithm}

+

 \begin{algorithm}{Bit Operations}

 	\begin{expandtable}

 	\begin{tabularx}{\linewidth}{|Ll|}

@@ -31,19 +44,6 @@
 	\sourcecode{other/bitOps.cpp}

 \end{algorithm}

 

-\begin{algorithm}{Overflow-sichere arithmetische Operationen}

-	Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.

-	\begin{expandtable}

-		\begin{tabularx}{\linewidth}{|lR|}

-			\hline

-			Addition & \code{__builtin_saddll_overflow(a, b, \&c)} \\

-			Subtraktion & \code{__builtin_ssubll_overflow(a, b, \&c)} \\

-			Multiplikation & \code{__builtin_smulll_overflow(a, b, \&c)} \\

-			\hline

-		\end{tabularx}

-	\end{expandtable}

-\end{algorithm}

-

 \begin{algorithm}{Pragmas}

 	\sourcecode{other/pragmas.cpp}

 \end{algorithm}

@@ -72,6 +72,12 @@
 	\sourcecode{other/sos.cpp}

 \end{algorithm}

 

+\begin{algorithm}{Fast Subset Sum}

+	\method{fastSubsetSum}{findet maximale subset $\mathit{sum}\leq t$}{n \cdot A}

+	Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.

+	\sourcecode{other/fastSubsetSum.cpp}

+\end{algorithm}

+

 \begin{algorithm}{Parallel Binary Search}

 	\sourcecode{other/pbs.cpp}

 \end{algorithm}

diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp
index 7cb60e5..f4db2fd 100644
--- a/content/other/pbs.cpp
+++ b/content/other/pbs.cpp
@@ -1,19 +1,19 @@
 // Q = # of queries, bucket sort is sometimes faster
-vector<int> low(Q, 0), high(Q, MAX_OPERATIONS);
+vector<int> low(Q, -1), high(Q, MAX_OPERATIONS);
 while (true) {
 	vector<pair<int, int>> focus;
-	for (int i = 0; i < Q; i++) if (low[i] < high[i]) {
-		focus.emplace_back((low[i] + high[i]) / 2, i);
-	}
+	for (int i = 0; i < Q; i++) {
+		if (low[i] + 1 < high[i]) {
+			focus.emplace_back((low[i] + high[i]) / 2, i);
+	}}
 	if (focus.empty()) break;
 	sort(all(focus));
 
 	// reset simulation
 	for (int step = 0; auto [mid, i] : focus) {
-		while (step <= mid) {
+		for (; step <= mid; step++) {
 			// simulation step
-			step++;
 		}
 		if (/* requirement already fulfilled */) high[i] = mid;
-		else low[i] = mid + 1;
-}} // answer in low (and high)
+		else low[i] = mid;
+}} // answer in low (MAX_OPERATIONS if never ok)
diff --git a/content/other/stuff.cpp b/content/other/stuff.cpp
index 41543ad..e4e37e2 100644
--- a/content/other/stuff.cpp
+++ b/content/other/stuff.cpp
@@ -1,13 +1,7 @@
-// Alles-Header.
-#include <bits/stdc++.h>
-
 // Setzt deutsche Tastaturlayout / toggle mit alt + space
 setxkbmap de
 setxkbmap de,us -option grp:alt_space_toggle
 
-// Schnelle Ein-/Ausgabe mit cin/cout.
-cin.tie(nullptr)->ios::sync_with_stdio(false);
-
 // Set mit eigener Sortierfunktion.
 set<point2, decltype(comp)> set1(comp);
 
diff --git a/content/string/ahoCorasick.cpp b/content/string/ahoCorasick.cpp
index eac312c..390d16d 100644
--- a/content/string/ahoCorasick.cpp
+++ b/content/string/ahoCorasick.cpp
@@ -4,7 +4,7 @@ struct AhoCorasick {
 		int suffix = 0, ch, cnt = 0;
 		array<int, ALPHABET_SIZE> nxt = {};
 
-		vert(int p, int c) : suffix(-p), ch(c) {}
+		vert(int p, int c) : suffix(-p), ch(c) {fill(all(nxt), -1);}
 	};
 	vector<vert> aho = {{0, -1}};
 
@@ -12,7 +12,7 @@ struct AhoCorasick {
 		int v = 0;
 		for (auto c : s) {
 			int idx = c - OFFSET;
-			if (!aho[v].nxt[idx]) {
+			if (aho[v].nxt[idx] == -1) {
 				aho[v].nxt[idx] = sz(aho);
 				aho.emplace_back(v, idx);
 			}
@@ -30,8 +30,8 @@ struct AhoCorasick {
 	}
 
 	int go(int v, int idx) { // Root is v=0, idx is char - OFFSET
-		if (aho[v].nxt[idx]) return aho[v].nxt[idx];
-		else return v == 0 ? 0 : go(getSuffix(v), idx);
+		if (aho[v].nxt[idx] != -1) return aho[v].nxt[idx];
+		return v == 0 ? 0 : aho[v].nxt[idx] = go(getSuffix(v), idx);
 	}
 
 	vector<vector<int>> adj;
diff --git a/content/string/duval.cpp b/content/string/duval.cpp
index bf36cce..253bae1 100644
--- a/content/string/duval.cpp
+++ b/content/string/duval.cpp
@@ -6,9 +6,8 @@ vector<pair<int, int>> duval(const string& s) {
 			if (s[k] < s[j]) k = i;
 			else k++;
 		}
-		while (i <= k) {
+		for (; i <= k; i += j - k) {
 			res.push_back({i, i + j - k});
-			i += j - k;
 	}}
 	return res;
 }
@@ -16,6 +15,5 @@ vector<pair<int, int>> duval(const string& s) {
 int minrotation(const string& s) {
 	auto parts = duval(s+s);
 	for (auto [l, r] : parts) {
-		if (l < sz(s) && r >= sz(s)) {
-			return l;
-}}}
+		if (r >= sz(s)) return l;
+}}
diff --git a/content/tcr.tex b/content/tcr.tex
index afac53c..3b686ef 100644
--- a/content/tcr.tex
+++ b/content/tcr.tex
@@ -1,6 +1,9 @@
-
-%maybe size 9pt if too many pages
-\documentclass[a4paper,fontsize=7.8pt]{scrartcl}
+\documentclass[
+	paper=a4,
+	DIV=calc,
+	fontsize=7.8pt,
+	usegeometry
+]{scrartcl}
 
 % General information.
 \newcommand{\teamname}{Infinite Loopers}
@@ -54,11 +57,7 @@
   \input{graph/graph}
   \input{geometry/geometry}
   \input{math/math}
-\end{multicols*}
   \clearpage
-  \input{math/tables}
-\begin{multicols*}{3}
-  \raggedcolumns
   \input{string/string}
   \input{python/python}
   \input{other/other}
diff --git a/content/template/template.cpp b/content/template/template.cpp
index c9a492c..7430d23 100644
--- a/content/template/template.cpp
+++ b/content/template/template.cpp
@@ -7,9 +7,9 @@ using namespace std;
 
 using ll = long long;
 using ld = long double;
- 
+
 void solve() {}
- 
+
 int main() {
 	cin.tie(0)->sync_with_stdio(false);
 	cout << setprecision(16);
diff --git a/content/tests/gcc5bug.cpp b/content/tests/gcc5bug.cpp
index f49603e..6aaeea9 100644
--- a/content/tests/gcc5bug.cpp
+++ b/content/tests/gcc5bug.cpp
@@ -1,4 +1,4 @@
 //https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68203
 struct A {
-    pair<int, int> values[1000000];
+	pair<int, int> values[1000000];
 };
diff --git a/test/GNUmakefile b/test/GNUmakefile
index 10e3b34..5e57930 100644
--- a/test/GNUmakefile
+++ b/test/GNUmakefile
@@ -1,6 +1,7 @@
 
-TESTS = $(basename $(shell find . -type f -name '*.cpp'))
-CXX = g++ -std=gnu++20 -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror
+TESTS = $(basename $(shell find . -path ./awk -prune -o -type f -name '*.cpp' -print))
+AWK = $(basename $(shell find . -type f -name '*.awk'))
+CXX = g++ -std=gnu++20 -I awk/ -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror
 
 test: $(TESTS:=.ok)
 
@@ -8,11 +9,12 @@ missing:
 	@find ../content -name '*.cpp' | sed 's|^../content/||' \
 	  | while read -r f ; do [ -e "$$f" ] || echo "$$f" ; done \
 	  | sort > missing.tmp
-	@sort missing.ignore | comm -23 missing.tmp -
+	@sort missing.ignore | comm -3 missing.tmp -
 	@rm missing.tmp
 
 clean:
 	rm -f $(TESTS:=.test) $(TESTS:=.ok) $(TESTS:=.d)
+	rm -rf awk/
 
 %.ok: %.test
 	timeout --foreground --verbose 60 prlimit -s$$((1<<32)) ./$<
@@ -21,10 +23,14 @@ clean:
 %.test: %.cpp
 	$(CXX) -o $@ $<
 
-%.d: %.cpp
+awk/%: %.awk ../content/%
+	@mkdir -p $(dir $@)
+	awk -f $*.awk < ../content/$* > $@
+
+%.d: %.cpp $(addprefix awk/,$(AWK))
 	$(CXX) -M -MT '$*.test $*.d' -MF $@ $<
 
 .PHONY: test clean
-.SECONDARY: $(TESTS:=.test)
+.SECONDARY: $(TESTS:=.test) $(addprefix awk/,$(AWK))
 
 include $(TESTS:=.d)
diff --git a/test/datastructures/LCT.cpp b/test/datastructures/LCT.cpp
new file mode 100644
index 0000000..58d76d7
--- /dev/null
+++ b/test/datastructures/LCT.cpp
@@ -0,0 +1,198 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include <datastructures/LCT.cpp>
+
+struct Naive {
+	vector<set<int>> adj;
+	vector<ll> weight;
+	Naive(int n) : adj(n), weight(n, queryDefault) {}
+
+	pair<ll, bool> dfs_path(int from, int to, ll delta = queryDefault, int prev = -1) {
+		if (from == to) {
+			weight[from] += delta;
+			return {weight[from], true};
+		}
+		for (int x : adj[from]) {
+			if (x == prev) continue;
+			auto [res, seen] = dfs_path(x, to, delta, from);
+			if (seen) {
+				weight[from] += delta;
+				return {res + weight[from], true};
+			}
+		}
+		return {queryDefault, false};
+	}
+
+	bool connected(int x, int y) {
+		return dfs_path(x, y).second;
+	}
+
+	void link(int x, int y) {
+		adj[x].insert(y);
+		adj[y].insert(x);
+	}
+
+	void cut(int x, int y) {
+		adj[x].erase(y);
+		adj[y].erase(x);
+	}
+
+	int lca(int root, int a, int b) {
+		int res = -1;
+		auto dfs_lca = [&](auto&& self, int c, int prev = -1) -> pair<bool, bool>{
+			bool seenA = c == a;
+			bool seenB = c == b;
+			for (int x : adj[c]) {
+				if (x == prev) continue;
+				auto [tmpA, tmpB] = self(self, x, c);
+				seenA |= tmpA;
+				seenB |= tmpB;
+			}
+			if (seenA && seenB && res < 0) res = c;
+			return {seenA, seenB};
+		};
+		dfs_lca(dfs_lca, root);
+		return res;
+	}
+
+	ll query(int from, int to) {
+		return dfs_path(from, to).first;
+	}
+
+	void modify(int from, int to, ll delta) {
+		dfs_path(from, to, delta);
+	}
+
+	int random(int x) {
+		vector<int> seen;
+		auto dfs_comp = [&](auto&& self, int c, int prev = -1) -> void {
+			seen.push_back(c);
+			for (int x : adj[c]) {
+				if (x == prev) continue;
+				self(self, x, c);
+			}
+		};
+		dfs_comp(dfs_comp, x);
+		return seen[Random::integer<int>(sz(seen))];
+	}
+
+	int randomAdj(int x) {
+		if (adj[x].empty()) return -1;
+		vector<int> seen(all(adj[x]));
+		return seen[Random::integer<int>(sz(seen))];
+	}
+};
+
+void stress_test() {
+	ll queries = 0;
+	ll connected = 0;
+	ll link = 0;
+	ll lca = 0;
+	ll sum = 0;
+	ll modify = 0;
+	ll cut = 0;
+	for (int tries = 0; tries < 500; tries++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(100, 10'000);
+
+		LCT lct(n);
+		Naive naive(n);
+		for (int i = 0; i < m; i++) {
+			bool testConnected = Random::integer<int>(2) == 0;
+			bool testLink = Random::integer<int>(2) == 0;
+			bool testLCA = Random::integer<int>(2) == 0;
+			bool testSum = Random::integer<int>(2) == 0;
+			bool testModify = Random::integer<int>(2) == 0;
+			bool testCut = Random::integer<int>(2) == 0;
+
+			{
+				int a = Random::integer<int>(0, n);
+				int b = Random::integer<int>(0, n);
+
+				auto expected = naive.connected(a, b);
+				if (testConnected) {
+					connected++;
+					auto got = lct.connected(&lct.nodes[a], &lct.nodes[b]);
+					if (got != expected) cerr << "error: 1" << FAIL;
+				}
+
+				if (!expected && testLink) {
+					lct.link(&lct.nodes[a], &lct.nodes[b]);
+					naive.link(a, b);
+					link++;
+					expected = true;
+				}
+
+				if (testLCA && expected) {
+					int c = naive.random(a);
+					lct.makeRoot(&lct.nodes[c]);
+					auto gotLCA = lct.lca(&lct.nodes[a], &lct.nodes[b])->id;
+					auto expectedLCA = naive.lca(c, a, b);
+					if (gotLCA != expectedLCA) cerr << "error: 2" << FAIL;
+					lca++;
+				}
+
+				if (testSum && expected) {
+					auto gotSum = lct.query(&lct.nodes[a], &lct.nodes[b]);
+					auto expectedSum = naive.query(a, b);
+					if (gotSum != expectedSum) cerr << "error: 3" << FAIL;
+					sum++;
+				}
+
+				if (testModify && expected) {
+					ll w = Random::integer<ll>(-1000, 1000);
+					lct.modify(&lct.nodes[a], &lct.nodes[b], w);//must a and b directly connected??
+					naive.modify(a, b, w);
+					modify++;
+				}
+			}
+			{
+				int a = Random::integer<int>(0, n);
+				int b = naive.randomAdj(a);
+				if (b >= 0 && testCut) {
+					lct.cut(&lct.nodes[a], &lct.nodes[b]);
+					naive.cut(a, b);
+					cut++;
+				}
+			}
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+	cerr << "  connected: " << connected << endl;
+	cerr << "  link: " << link << endl;
+	cerr << "  lca: " << lca << endl;
+	cerr << "  sum: " << sum << endl;
+	cerr << "  modify: " << modify << endl;
+	cerr << "  cut: " << cut << endl;
+}
+
+constexpr int N = 200'000;
+constexpr int M = 500'000;
+void performance_test() {
+	timer t;
+	t.start();
+	LCT lct(N);
+	t.stop();
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		int a = Random::integer<int>(0, N);
+		int b = Random::integer<int>(0, N);
+		ll w = Random::integer<ll>(-1000, 1000);
+		
+		t.start();
+		if (!lct.connected(&lct.nodes[a], &lct.nodes[b])) {
+			lct.link(&lct.nodes[a], &lct.nodes[b]);
+		}
+		lct.modify(&lct.nodes[a], &lct.nodes[b], w);
+		hash += lct.query(&lct.nodes[a], &lct.nodes[b]);
+		t.stop();
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp
new file mode 100644
index 0000000..e0345af
--- /dev/null
+++ b/test/datastructures/dynamicConvexHull.cpp
@@ -0,0 +1,67 @@
+#include "../util.h"
+namespace dch {
+	constexpr ll INF = LL::INF;
+	#include <datastructures/dynamicConvexHull.cpp>
+}
+
+struct Line {
+	ll m, c;
+	Line(ll m_, ll c_) : m(m_), c(c_) {}
+	ll operator()(ll x) {return m*x+c;}
+};
+
+void stress_test(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+
+		vector<Line> naive;
+
+		dch::HullDynamic hd;
+		for (int i = 0; i < n; i++) {
+			ll m = Random::integer<ll>(-range, range);
+			ll c = Random::integer<ll>(-range, range);
+			hd.add(m, c);
+			naive.emplace_back(m, c);
+
+			for (int j = 0; j < 100; j++) {
+				ll x = Random::integer<ll>(-range, range);
+
+				ll got = hd.query(x);
+				ll expected = naive[0](x);
+				for (auto l : naive) expected = max(expected, l(x));
+
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	dch::HullDynamic hd;
+
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll m = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll c = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll x = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		
+		t.start();
+		hd.add(m, c);
+		hash += hd.query(x);
+		t.stop();
+	}
+	if (t.time > 200) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test(100);
+	stress_test(1'000);
+	stress_test(1'000'000);
+	performance_test();
+}
diff --git a/test/datastructures/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp
new file mode 100644
index 0000000..d50ca60
--- /dev/null
+++ b/test/datastructures/dynamicConvexHull.lichao.cpp
@@ -0,0 +1,37 @@
+#include "../util.h"
+constexpr ll INF = LL::INF;
+#include <datastructures/dynamicConvexHull.cpp>
+#include <datastructures/lichao.cpp>
+
+void stress_test(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+		xs = Random::distinct(n, -range, range);
+		sort(all(xs));
+
+		HullDynamic hd;
+		Lichao lichao;
+		for (int i = 0; i < 1000; i++) {
+			ll m = Random::integer<ll>(-range, range);
+			ll c = Random::integer<ll>(-range, range);
+			hd.add(m, c);
+			lichao.insert({-m, -c});
+
+			for (ll x : xs) {
+				ll gotA = hd.query(x);
+				ll gotB = -lichao.query(x);
+
+				if (gotA != gotB) cerr << "gotA: " << gotA << ", gotB: " << gotB << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+int main() {
+	stress_test(100);
+	stress_test(1'000);
+	stress_test(1'000'000);
+}
diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp
index d332dc8..bc0753f 100644
--- a/test/datastructures/fenwickTree2.cpp
+++ b/test/datastructures/fenwickTree2.cpp
@@ -9,7 +9,7 @@ void stress_test() {
 	ll queries = 0;
 	for (int tries = 0; tries < 100; tries++) {
 		int n = Random::integer<int>(10, 100);
-		vector<ll> naive(n);// = Random::integers<ll>(n, -1000, 1000);
+		vector<ll> naive = Random::integers<ll>(n, -1000, 1000);
 		init(naive);
 		for (int operations = 0; operations < 1000; operations++) {
 			{
diff --git a/test/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp
index 7b0e448..3030e1c 100644
--- a/test/datastructures/lazyPropagation.cpp
+++ b/test/datastructures/lazyPropagation.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll INF = LL::INF;
 #include <datastructures/lazyPropagation.cpp>
 
 constexpr int N = 1000'000;
diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp
new file mode 100644
index 0000000..f4b797b
--- /dev/null
+++ b/test/datastructures/lichao.cpp
@@ -0,0 +1,75 @@
+#include "../util.h"
+constexpr ll INF = LL::INF;
+#include <datastructures/lichao.cpp>
+
+void stress_test(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+		xs = Random::distinct<ll>(n, -range, range);
+		sort(all(xs));
+
+		vector<ll> naive(n, INF);
+		Lichao tree;
+
+		for (int operations = 0; operations < 1000; operations++) {
+			{
+				ll m = Random::integer<ll>(-100, 100);
+				ll c = Random::integer<ll>(-range, range);
+				ll l = Random::integer<ll>(-range, range);
+				ll r = Random::integer<ll>(-range, range);
+				Fun f{m, c};
+
+				tree.segmentInsert(f, l, r);
+				for (int i = 0; i < n; i++) {
+					if (l <= xs[i] && xs[i] < r) naive[i] = min(naive[i], f(i));
+				}
+			}
+			{
+				queries++;
+				int i = Random::integer<int>(0, n);
+				ll got = tree.query(xs[i]);
+				ll expected = naive[i];
+				if (got != expected) cerr << xs[i] << endl;
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+			}
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 200'000;
+void performance_test() {
+	timer t;
+	xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000);
+	sort(all(xs));
+
+	t.start();
+	Lichao tree;
+	t.stop();
+
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+
+		ll m = Random::integer<ll>(-1'000'000, 1'000'000);
+		ll c = Random::integer<ll>(-1'000'000, 1'000'000);
+		ll l = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll r = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll x = xs[Random::integer<int>(N)];
+		Fun f{m, c};
+
+		t.start();
+		tree.segmentInsert(f, l, r);
+		hash ^= tree.query(x);
+		t.stop();
+	}
+	if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test(100);
+	stress_test(1'000);
+	stress_test(1'000'000);
+	performance_test();
+}
diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp
new file mode 100644
index 0000000..3ae7c4d
--- /dev/null
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -0,0 +1,132 @@
+#include "../util.h"
+#include <datastructures/monotonicConvexHull.cpp>
+
+struct Line {
+	ll m, c;
+	Line(ll m_, ll c_) : m(m_), c(c_) {}
+	ll operator()(ll x) {return m*x+c;}
+};
+
+void stress_test(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+		auto ms = Random::integers<ll>(n, -range, range);
+		sort(all(ms), greater<>{});
+		auto cs = ms;
+		for (int l = 0, r = 0; l < n;) {
+			while (r < n && ms[l] == ms[r]) r++;
+			auto tmp = Random::distinct<ll>(r - l, -range, range);
+			sort(all(tmp), greater<>{});
+			for (int c : tmp) {
+				cs[l] = c;
+				l++;
+			}
+		}
+
+		auto xs = Random::integers<ll>(n*100, -range*n, range*n);
+		sort(all(xs));
+		int i = 0;
+
+		vector<Line> naive;
+
+		Envelope mch;
+		for (int k = 0; k < n; k++) {
+			ll m = ms[k];
+			ll c = cs[k];
+
+			mch.add(m, c);
+			naive.emplace_back(m, c);
+
+			for (int j = i + 100; i < j; i++) {
+				ll x = xs[i];
+
+				ll got = mch.query(x);
+				ll expected = naive[0](x);
+				for (auto l : naive) expected = min(expected, l(x));
+
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+void stress_test_independent(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+		auto ms = Random::integers<ll>(n, -range, range);
+		sort(all(ms), greater<>{});
+		auto cs = ms;
+		for (int l = 0, r = 0; l < n;) {
+			while (r < n && ms[l] == ms[r]) r++;
+			auto tmp = Random::distinct<ll>(r - l, -range, range);
+			sort(all(tmp), greater<>{});
+			for (int c : tmp) {
+				cs[l] = c;
+				l++;
+			}
+		}
+
+		vector<Line> naive;
+
+		Envelope mch;
+		for (int i = 0; i < n; i++) {
+			ll m = ms[i];
+			ll c = cs[i];
+
+			mch.add(m, c);
+			naive.emplace_back(m, c);
+
+			auto xs = Random::integers<ll>(100, -range, range);
+			sort(all(xs));
+			auto tmp = mch;
+
+			for (auto x : xs) {
+				ll got = tmp.query(x);
+				ll expected = naive[0](x);
+				for (auto l : naive) expected = min(expected, l(x));
+
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random independent queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	auto ms = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000);
+	sort(all(ms), greater<>{});
+	auto xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000);
+	sort(all(xs));
+	Envelope mch;
+
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll c = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll m = ms[operations];
+		ll x = xs[operations];
+
+		t.start();
+		mch.add(m, c);
+		hash += mch.query(x);
+		t.stop();
+	}
+	if (t.time > 100) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test(100);
+	stress_test(1'000);
+	stress_test(1'000'000);
+	stress_test_independent(100);
+	stress_test_independent(1'000);
+	stress_test_independent(1'000'000);
+	performance_test();
+}
diff --git a/test/datastructures/persistent.cpp b/test/datastructures/persistent.cpp
new file mode 100644
index 0000000..4e304fa
--- /dev/null
+++ b/test/datastructures/persistent.cpp
@@ -0,0 +1,35 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include <datastructures/persistent.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+
+		int timeRef = Random::integer<int>(1, 30);
+		persistent<double> got(timeRef);
+		map<int, double> expected;
+
+		for (int i = 0; i < n; i++) {
+			timeRef += Random::integer<int>(1, 30);
+			double x = Random::real<double>(-1'000, 1'000);
+			auto t = got.set(x);
+
+			if (!expected.empty() && t <= expected.rbegin()->first) cerr << "error: time travel" << FAIL;
+			expected[t] = x;
+		}
+
+		double tmp = 0;
+		for (int i = expected.begin()->first; i < expected.rbegin()->first + 10; i++) {
+			if (expected.find(i) != expected.end()) tmp = expected[i];
+			if (got.get(i) != tmp) cerr << "got: " << got.get(i) << ", " << "expected: " << tmp << FAIL;
+		}
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+int main() {
+	stress_test();
+}
diff --git a/test/datastructures/persistentArray.cpp b/test/datastructures/persistentArray.cpp
new file mode 100644
index 0000000..6712089
--- /dev/null
+++ b/test/datastructures/persistentArray.cpp
@@ -0,0 +1,48 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include <datastructures/persistent.cpp>
+#include <datastructures/persistentArray.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 2'000; tries++) {
+		int n = Random::integer<int>(1, 30)*1000;
+		int m = Random::integer<int>(1, 30);
+
+		persistentArray<double> got(m);
+		vector<double> cur(m);
+		vector<pair<int, vector<double>>> expected;
+		for (int i = 0; i < n; i++) {
+			int op = Random::integer<int>(0, 20);
+			if (op <= 10) {
+				int j = Random::integer<int>(0, m);
+				double x = Random::real<double>(-1'000, 1'000);
+
+				auto t = got.set(j, x);
+				if (!expected.empty() && t <= expected.rbegin()->first) cerr << "error: time travel" << FAIL;
+
+				cur[j] = x;
+				expected.emplace_back(t, cur);
+			} else if (op <= 16) {
+				if (sz(expected) < 1) continue;
+				int j = Random::integer<int>(0, sz(expected));
+				for (int k = 0; k < m; k++) {
+					if (got.get(k, expected[j].first) != expected[j].second[k]) cerr << "got: " << got.get(k, expected[j].first) << ", expected: " << expected[j].second[k] << FAIL;
+				}
+			} else {
+				if (sz(expected) < 1) continue;
+				int j = Random::integer<int>(0, sz(expected));
+				got.reset(expected[j].first);
+				expected.resize(j + 1);
+				cur = expected.back().second;
+			}
+			
+		}
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+int main() {
+	stress_test();
+}
diff --git a/test/datastructures/stlRope.cpp b/test/datastructures/stlRope.cpp
new file mode 100644
index 0000000..7405e4e
--- /dev/null
+++ b/test/datastructures/stlRope.cpp
@@ -0,0 +1,6 @@
+#include "../util.h"
+#include <datastructures/stlRope.cpp>
+
+int main() {
+	test();
+}
diff --git a/test/datastructures/stlRope.cpp.awk b/test/datastructures/stlRope.cpp.awk
new file mode 100644
index 0000000..df7c361
--- /dev/null
+++ b/test/datastructures/stlRope.cpp.awk
@@ -0,0 +1,27 @@
+/rope<int> v;/ {
+	print "void test() {"
+	print "ll num = 5;"
+	print "ll start = 2;"
+	print "ll length = 4;"
+	print "ll offset = 3;"
+}
+/v.push_back(num);/ {
+	print "v.push_back(0);"
+	print "v.push_back(1);"
+	print "v.push_back(2);"
+	print "v.push_back(3);"
+	print "v.push_back(4);"
+}
+/rope<int> sub/ {
+	print "v.push_back(6);"
+	print "v.push_back(7);"	
+}
+/for\(auto it/ {
+	print "vector<int> got, expected = {0,1,6,2,3,4,5,7};"
+}
+END {
+	print "	got.push_back(*it);"
+	print "if (got != expected) cerr << \"error\" << endl;"
+	print "}"
+}
+{ print }
diff --git a/test/datastructures/treap.cpp b/test/datastructures/treap.cpp
new file mode 100644
index 0000000..2fc9d63
--- /dev/null
+++ b/test/datastructures/treap.cpp
@@ -0,0 +1,85 @@
+#include "../util.h"
+#include <datastructures/treap.cpp>
+
+void add(Treap& t, vector<ll>& ans, int v) {
+    if (v < 0) return;
+    add(t, ans, t.treap[v].l);
+    ans.push_back(t.treap[v].val);
+    add(t, ans, t.treap[v].r);
+}
+
+vector<ll> to_vec(Treap& t) {
+    vector<ll> ans;
+    add(t, ans, t.root);
+    return ans;
+}
+
+void stress_test(int T, int n) {
+	for (int tries = 0; tries < T; tries++) {
+		int ins = Random::integer<int>(1, n);
+        int rem = Random::integer<int>(0, ins+1);
+
+        vector<ll> a;
+        Treap t;
+        while (ins + rem > 0) {
+            bool is_ins = Random::integer(0, ins+rem) < ins;
+            if (a.empty()) is_ins = true;
+
+            if (is_ins) {
+                int ind = Random::integer<int>(0, (int)sz(a)+1);
+                ll val = Random::integer((ll)-1e18, (ll)1e18+1);
+                t.insert(ind, val);
+                a.insert(a.begin() + ind, val);
+                ins--;
+            } else {
+                int ind = Random::integer<int>(0, (int)sz(a));
+                int cnt = Random::integer<int>(1, 1 + min<int>({(int)sz(a)-ind, rem, (int)sqrt(n)}));
+                t.remove(ind, cnt);
+                a.erase(a.begin() + ind, a.begin() + ind + cnt);
+                rem -= cnt;
+            }
+        }
+        if (to_vec(t) != a) cerr << "Failed stress test" << FAIL;
+	}
+	cerr << "Tested " << T << " random tests with n<=" << n << endl;
+}
+
+constexpr int N = 200'000;
+void performance_test() {
+	timer t;
+
+	t.start();
+	Treap tr;
+	t.stop();
+
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+        int ind = Random::integer<int>(0, operations+1);
+        ll val = Random::integer((ll)-1e18, (ll)1e18+1);
+
+		t.start();
+        tr.insert(ind, val);
+		hash ^= tr.root;
+		t.stop();
+	}
+    while (tr.root != -1) {
+        t.start();
+        int sz = tr.getSize(tr.root);
+        t.stop();
+
+        int ind = Random::integer<int>(0, sz);
+        int cnt = Random::integer<int>(1, 1 + min<int>(sz-ind, 10));
+        t.start();
+        tr.remove(ind, cnt);
+        t.stop();
+    }
+	if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test(10000, 10);
+	stress_test(1000, 100);
+	stress_test(100, 10000);
+	performance_test();
+}
diff --git a/test/geometry.h b/test/geometry.h
index 7886fe2..0167d5c 100644
--- a/test/geometry.h
+++ b/test/geometry.h
@@ -1,6 +1,6 @@
-#include <geometry/sortAround.cpp>
-
 namespace details {
+	#include <geometry/sortAround.cpp>
+
 	// Liegt p auf der Strecke a-b?
 	bool pointInLineSegment(pt a, pt b, pt p) {
 		if (cross(a, b, p) != 0) return false;
@@ -59,7 +59,7 @@ namespace Random {
 			for (size_t i = 0; i < dirs.size(); i++) {
 				dirs[i] = pt(x[i], y[i]);
 			}
-			sortAround(0, dirs);
+			details::sortAround(0, dirs);
 
 			vector<pt> res = {{0, 0}};
 			ll maxX = 0;
diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp
index 7f8ec30..5740b95 100644
--- a/test/geometry/delaunay.cpp
+++ b/test/geometry/delaunay.cpp
@@ -16,11 +16,11 @@ vector<pt> convexHull(vector<pt> pts){
 	vector<pt> h(2 * sz(pts));
 	auto half = [&](auto begin, auto end, int t) {
 		for (auto it = begin; it != end; it++) {
-			while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--;//allow collinear points!
+			while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--; //allow collinear points!
 			h[k++] = *it;
 	}};
-	half(all(pts), 1);// Untere Hülle.
-	half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle.
+	half(all(pts), 1); // Untere Hülle.
+	half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle.
 	h.resize(k);
 	return h;
 }
diff --git a/test/geometry/formulas3d.cpp b/test/geometry/formulas3d.cpp
new file mode 100644
index 0000000..f6c04b7
--- /dev/null
+++ b/test/geometry/formulas3d.cpp
@@ -0,0 +1,236 @@
+#include "../util.h"
+constexpr double EPS = 1e-6;
+struct pt3 {
+	double x, y, z;
+	pt3 operator-(const pt3 o) const {
+		return {x-o.x, y-o.y, z-o.z};
+	}
+	pt3 operator+(const pt3 o) const {
+		return {x+o.x, y+o.y, z+o.z};
+	}
+
+	pt3 operator*(double m) const {
+		return {x*m, y*m, z*m};
+	}
+
+	pt3 operator/(double d) const {
+		return {x/d, y/d, z/d};
+	}
+
+	friend ostream& operator<<(ostream& os, pt3 p) {
+		return os << "(" << p.x << ", " << p.y << ", " << p.z << ")";
+	}
+};
+
+pt3 cross(pt3 a, pt3 b);
+double abs(pt3 p);
+double distToLine(pt3 a, pt3 b, pt3 p) {
+	return abs(cross(p - a, b - a)) / abs(b - a);
+}
+
+#include <geometry/formulas3d.cpp>
+
+namespace Random {
+	pt3 point3d(ll l, ll r) {
+		return {
+			(double)integer<ll>(l, r),
+			(double)integer<ll>(l, r),
+			(double)integer<ll>(l, r),
+		};
+	}
+
+	template<size_t C>
+	std::array<pt3, C> distinct(ll l, ll r) {
+		std::array<pt3, C> res = {};
+		for (size_t i = 0; i < C; i++) {
+			bool unqiue;
+			do {
+				res[i] = point3d(l, r);
+				unqiue = true;
+				for (size_t j = 0; j < i; j++) {
+					unqiue &= res[j].x != res[i].x ||
+					          res[j].y != res[i].y ||
+					          res[j].z != res[i].z;
+				}
+			} while (!unqiue);
+		}
+		return res;
+	}
+}
+
+void test_dot(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto p = Random::point3d(-range, range);
+		auto q = Random::point3d(-range, range);
+
+		auto expected = p.x*q.x + p.y*q.y + p.z*q.z;
+		auto got = dot(p, q);
+
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested dot: " << queries << endl;
+}
+
+void test_cross(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto p = Random::point3d(-range, range);
+		auto q = Random::point3d(-range, range);
+
+		auto expected = pt3{p.y*q.z - p.z*q.y,
+		                    p.z*q.x - p.x*q.z,
+		                    p.x*q.y - p.y*q.x};
+		auto got = cross(p, q);
+
+		if (got.x != expected.x) cerr << "error: x" << FAIL;
+		if (got.y != expected.y) cerr << "error: y" << FAIL;
+		if (got.z != expected.z) cerr << "error: z" << FAIL;
+		queries++;
+	}
+	cerr << "tested cross: " << queries << endl;
+}
+
+void test_abs(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto p = Random::point3d(-range, range);
+
+		auto expected = sqrt(p.x*p.x + p.y*p.y + p.z*p.z);
+		auto got = abs(p);
+
+		if (abs(got - expected) > 1e-6) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested abs: " << queries << endl;
+}
+
+void test_mixed(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto a = Random::point3d(-range, range);
+		auto b = Random::point3d(-range, range);
+		auto c = Random::point3d(-range, range);
+
+		auto expected = dot(cross(a, b), c);
+		auto got = mixed(a, b, c);
+
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested mixed: " << queries << endl;
+}
+
+void test_ccw(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto a = Random::point3d(-range, range);
+		auto b = Random::point3d(-range, range);
+		auto c = Random::point3d(-range, range);
+		auto d = Random::point3d(-range, range);
+
+		ll expected = mixed(b - a, c - a, d - a);
+		if (expected < 0) expected = -1;
+		if (expected > 0) expected = 1;
+		auto got = ccw(a, b, c, d);
+
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested ccw: " << queries << endl;
+}
+
+void test_distToPlane(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto [p, q] = Random::distinct<2>(-range, range);
+		auto [a, b, c] = Random::distinct<3>(-range, range);
+
+		auto norm = cross(a - c, b - c);
+		norm = norm / abs(norm);
+
+		auto gotA = distToPlane(a, b, c, p);
+		auto gotB = distToPlane(a, b, c, q);
+		auto got = ccw(a, b, c, p) * ccw(a, b, c, q) < 0 ? gotA + gotB : abs(gotA - gotB);
+
+		auto expected = abs(dot(norm, p - q));
+
+		if (abs(got - expected) > 1e-6) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested distToPlane: " << queries << endl;
+}
+
+void stress_pointOnPlane(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto p = Random::point3d(-range, range);
+		auto [a, b, c] = Random::distinct<3>(-range, range);
+
+		bool expected = ccw(a, b, c, p) == 0;
+		bool got = pointOnPlane(a, b, c, p);
+
+		if (got != expected) cerr << "error" << FAIL;
+		queries++;
+	}
+	cerr << "tested pointOnPlane: " << queries << endl;
+}
+
+void test_linePlaneIntersection(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto [p, q] = Random::distinct<2>(-range, range);
+		auto [a, b, c] = Random::distinct<3>(-range, range);
+
+		if (abs(dot(p - q, cross(a-c, b-c))) < 1e-6) continue; 
+
+		auto got = linePlaneIntersection(p, q, a, b, c);
+
+		if (distToLine(p, q, got) > 1e-6) cerr << "error: 1" << FAIL;
+		if (distToPlane(a, b, c, got) > 1e-6) cerr << "error: 2" << FAIL;
+		queries++;
+	}
+	cerr << "tested linePlaneIntersection: " << queries << endl;
+}
+
+void test_lineLineDist(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto [p, q] = Random::distinct<2>(-range, range);
+		auto [a, b] = Random::distinct<2>(-range, range);
+
+		double expected = 0;
+		if (ccw(a, b, p, q) != 0) {
+			pt3 c = a + p - q;
+			expected = distToPlane(a, b, c, p);
+		}
+		auto got = lineLineDist(p, q, a, b);
+		
+		if (abs(got - expected) > 1e-6) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested lineLineDist: " << queries << endl;
+}
+
+int main() {
+	test_dot(100);
+	test_dot(1'000'000);
+	test_cross(100);
+	test_cross(1'000'000);
+	test_abs(100);
+	test_abs(1'000'000);
+	test_mixed(100);
+	test_mixed(1'000'000);
+	test_ccw(100);
+	test_ccw(1'000'000);
+
+	test_distToPlane(100);
+	test_distToPlane(1'000'000);
+	stress_pointOnPlane(100);
+	stress_pointOnPlane(1'000'000);
+	test_linePlaneIntersection(100);
+	test_linePlaneIntersection(1'000);//can be far away
+	test_lineLineDist(100);
+	test_lineLineDist(1'000'000);
+}
diff --git a/test/geometry/hpi.cpp b/test/geometry/hpi.cpp
new file mode 100644
index 0000000..a2326bc
--- /dev/null
+++ b/test/geometry/hpi.cpp
@@ -0,0 +1,291 @@
+#include "../util.h"
+constexpr ll EPS = 0;
+#define double ll
+#define polar polar<ll>
+#include <geometry/formulas.cpp>
+#undef polar
+#undef double
+#include "../geometry.h"
+ll sgn(ll x) {
+	return (x > 0) - (x < 0);
+}
+#include <geometry/hpi.cpp>
+
+//https://cp-algorithms.com/geometry/halfplane-intersection.html
+namespace cpalgo {
+	// Redefine epsilon and infinity as necessary. Be mindful of precision errors.
+	const long double eps = 1e-9, inf = 1e9; 
+
+	// Basic point/vector struct.
+	struct Point { 
+
+		long double x, y;
+		explicit Point(long double x_ = 0, long double y_ = 0) : x(x_), y(y_) {}
+		Point(pt p) : x(real(p)), y(imag(p)) {}
+
+		// Addition, substraction, multiply by constant, dot product, cross product.
+
+		friend Point operator + (const Point& p, const Point& q) {
+			return Point(p.x + q.x, p.y + q.y); 
+		}
+
+		friend Point operator - (const Point& p, const Point& q) { 
+			return Point(p.x - q.x, p.y - q.y); 
+		}
+
+		friend Point operator * (const Point& p, const long double& k) { 
+			return Point(p.x * k, p.y * k); 
+		} 
+
+		friend long double dot(const Point& p, const Point& q) {
+			return p.x * q.x + p.y * q.y;
+		}
+
+		friend long double cross(const Point& p, const Point& q) { 
+			return p.x * q.y - p.y * q.x; 
+		}
+
+		friend std::ostream& operator<<(std::ostream& os, const Point& p) {
+			return os << "(" << p.x << ", " << p.y << ")";
+		}
+
+
+	};
+
+	// Basic half-plane struct.
+	struct Halfplane { 
+
+		// 'p' is a passing point of the line and 'pq' is the direction vector of the line.
+		Point p, pq; 
+		long double angle;
+
+		Halfplane() {}
+		Halfplane(const Point& a, const Point& b) : p(a), pq(b - a) {
+			angle = atan2l(pq.x, -pq.y);//patched to get same sort
+		}
+		Halfplane(array<pt, 2> ps) : Halfplane(ps[0], ps[1]) {}
+		Halfplane(hp h) : Halfplane(h.from, h.to) {}
+
+		// Check if point 'r' is outside this half-plane. 
+		// Every half-plane allows the region to the LEFT of its line.
+		bool out(const Point& r) {
+			return cross(pq, r - p) < -eps; 
+		}
+
+		// Comparator for sorting. 
+		bool operator < (const Halfplane& e) const { 
+			return angle < e.angle;
+		} 
+
+		// Intersection point of the lines of two half-planes. It is assumed they're never parallel.
+		friend Point inter(const Halfplane& s, const Halfplane& t) {
+			long double alpha = cross((t.p - s.p), t.pq) / cross(s.pq, t.pq);
+			return s.p + (s.pq * alpha);
+		}
+
+		friend std::ostream& operator<<(std::ostream& os, const Halfplane& hp) {
+			return os << hp.p << " " << hp.p+hp.pq;
+		}
+	};
+
+	// Actual algorithm
+	vector<Point> hp_intersect(vector<Halfplane>& H) { 
+
+		/*Point box[4] = {  // Bounding box in CCW order
+			Point(inf, inf), 
+			Point(-inf, inf), 
+			Point(-inf, -inf), 
+			Point(inf, -inf) 
+		};
+
+		for(int i = 0; i<4; i++) { // Add bounding box half-planes.
+			Halfplane aux(box[i], box[(i+1) % 4]);
+			H.push_back(aux);
+		}*/
+		// Add bounding box half-planes, fixed:
+		H.push_back({pt( 1e9,  1e9), pt( 1e9-1,  1e9  )});
+		H.push_back({pt(-1e9,  1e9), pt(-1e9  ,  1e9-1)});
+		H.push_back({pt(-1e9, -1e9), pt(-1e9+1, -1e9  )});
+		H.push_back({pt( 1e9, -1e9), pt( 1e9  , -1e9+1)});
+
+		// Sort by angle and start algorithm
+		sort(H.begin(), H.end());
+		deque<Halfplane> dq;
+		int len = 0;
+		for(int i = 0; i < int(H.size()); i++) {
+
+			// Remove from the back of the deque while last half-plane is redundant
+			while (len > 1 && H[i].out(inter(dq[len-1], dq[len-2]))) {
+				dq.pop_back();
+				--len;
+			}
+
+			// Remove from the front of the deque while first half-plane is redundant
+			while (len > 1 && H[i].out(inter(dq[0], dq[1]))) {
+				dq.pop_front();
+				--len;
+			}
+
+			// Special case check: Parallel half-planes
+			if (len > 0 && fabsl(cross(H[i].pq, dq[len-1].pq)) < eps) {
+				// Opposite parallel half-planes that ended up checked against each other.
+				if (dot(H[i].pq, dq[len-1].pq) < 0.0)
+					return vector<Point>();
+
+				// Same direction half-plane: keep only the leftmost half-plane.
+				if (H[i].out(dq[len-1].p)) {
+					dq.pop_back();
+					--len;
+				}
+				else continue;
+			}
+
+			// Add new half-plane
+			dq.push_back(H[i]);
+			++len;
+		}
+
+		// Final cleanup: Check half-planes at the front against the back and vice-versa
+		while (len > 2 && dq[0].out(inter(dq[len-1], dq[len-2]))) {
+			dq.pop_back();
+			--len;
+		}
+
+		while (len > 2 && dq[len-1].out(inter(dq[0], dq[1]))) {
+			dq.pop_front();
+			--len;
+		}
+
+		// Report empty intersection if necessary
+		if (len < 3) return vector<Point>();
+
+		// Reconstruct the convex polygon from the remaining half-planes.
+		vector<Point> ret(len);
+		for(int i = 0; i+1 < len; i++) {
+			ret[i] = inter(dq[i], dq[i+1]);
+		}
+		ret.back() = inter(dq[len-1], dq[0]);
+		return ret;
+	}
+}
+
+//check if a is dominated by b and c
+bool naiveCheck(cpalgo::Halfplane a, cpalgo::Halfplane b, cpalgo::Halfplane c) {
+	return a.out(inter(b, c));
+}
+
+void test_check(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto a = Random::line(range);
+		auto b = Random::line(range);
+		auto c = b;
+		while (cross(b[0] - b[1], c[0] - c[1]) == 0) c = Random::line(range);
+		
+		bool got = hp(a[0], a[1]).check(hp(b[0], b[1]), hp(c[0], c[1]));
+		bool expected = naiveCheck(a, b, c);
+
+		if (got != expected) {
+			cout << tries << endl;
+			cout << a[0] << " " << a[1] << endl;
+			cout << b[0] << " " << b[1] << endl;
+			cout << c[0] << " " << c[1] << endl;
+			cout << boolalpha << got << " " << expected << endl;
+			cerr << "error" << FAIL;
+		}
+		queries++;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+void stress_test(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto centre = Random::point<ll>(-range / 2, range / 2);
+		int n = Random::integer<int>(3, 30);
+
+		vector<hp> hps1 = {//+cpalgo bounding box
+			{pt( 1e9,  1e9), pt(-1e9,  1e9)},
+			{pt(-1e9,  1e9), pt(-1e9, -1e9)},
+			{pt(-1e9, -1e9), pt( 1e9, -1e9)},
+			{pt( 1e9, -1e9), pt( 1e9,  1e9)},
+		};
+
+		vector<cpalgo::Halfplane> hps2;
+		for (int i = 0; i < n; i++) {
+			auto [a, b] = Random::line(range);
+			if (cross(a, b, centre) < 0) swap(a, b);
+			hps1.emplace_back(a, b);
+			hps2.emplace_back(a, b);
+		}
+
+		auto expected = cpalgo::hp_intersect(hps2);
+		auto gotHp = intersect(hps1);
+		if (sz(gotHp) == 1) cerr << "WHAT?" << FAIL;
+		for (hp h : gotHp) {
+			if (h.dummy()) cerr << "DUMMY!" << FAIL;//we added a bounding box...
+		}
+		vector<cpalgo::Point> got;
+		if (!gotHp.empty()) {
+			gotHp.push_back(gotHp[0]);
+			for (int i = 0; i + 1 < sz(gotHp); i++) {
+				got.push_back(inter(cpalgo::Halfplane(gotHp[i]), cpalgo::Halfplane(gotHp[i + 1])));
+			}
+		}
+
+		bool eq = sz(got) == sz(expected);
+		for (ll i = 0; eq && i < sz(got); i++) {
+			eq &= float_error(got[i].x, expected[i].x) < 1e-6;
+			eq &= float_error(got[i].y, expected[i].y) < 1e-6;
+		}
+
+		if (!eq) {
+			cerr << tries << endl;
+			cerr << setprecision(20) << endl;
+			for (auto tmp : hps2) cerr << tmp << endl;
+			cerr << endl;
+			for (auto tmp : expected) cerr << tmp << endl;
+			cerr << endl;
+			for (auto tmp : got) cerr << tmp << endl;
+			cerr << FAIL;
+		}
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+/*constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	double maxTime = 0;
+
+	vector<pt> ps;
+	for (int i = 0; i*i <= N; i++) {
+		for (int j = 0; j*j <= N; j++) {
+			ps.emplace_back(i, j);
+		}
+	}
+	t.start();
+	hash = shortestDist(ps);
+	t.stop();
+	maxTime = max(maxTime, t.time);
+
+	ps = Random::points<ll>(N, -1'000'000'000, 1'000'000'000);
+	t.reset();
+	t.start();
+	hash += shortestDist(ps);
+	t.stop();
+	maxTime = max(maxTime, t.time);
+
+	if (maxTime > 500) cerr << "too slow: " << maxTime << FAIL;
+	cerr << "tested performance: " << maxTime << "ms (hash: " << hash << ")" << endl;
+}*/
+
+int main() {
+	test_check(10);
+	test_check(100);
+	stress_test(10);
+	stress_test(100);
+	//performance_test();
+}
diff --git a/test/geometry/lines.cpp b/test/geometry/lines.cpp
new file mode 100644
index 0000000..7b1b99a
--- /dev/null
+++ b/test/geometry/lines.cpp
@@ -0,0 +1,107 @@
+#include "../util.h"
+constexpr double EPS = 1e-6;
+#define ll double
+double gcd(double x, double /**/) {return x;} //hacky
+#include <geometry/formulas.cpp>
+#undef ll
+#include <geometry/linesAndSegments.cpp>
+#include <geometry/lines.cpp>
+
+#include "../geometry.h"
+
+void stress_pointsToLine(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto [a, b] = Random::line(range);
+
+		line gotA(a, b);
+		if (real(a) != real(b)) {
+			gotA.a /= gotA.b;
+			gotA.c /= gotA.b;
+			gotA.b /= gotA.b;
+		} else {
+			gotA.c /= gotA.a;
+			gotA.a /= gotA.a;
+		}
+		line gotB = pointsToLine(a, b);
+
+		if (!same(gotA, gotB)) cerr << "error" << FAIL;
+		queries++;
+	}
+	cerr << "tested pointsToLine: " << queries << endl;
+}
+
+void stress_same(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto [a, b] = Random::line(range);
+		auto [c, d] = Random::line(range);
+
+		line lAB = pointsToLine(a, b);
+		line lCD = pointsToLine(c, d);
+
+		auto got = same(lAB, lCD);
+		auto expected = pointOnLine(a, b, c) && pointOnLine(a, b, d);
+
+		if (got != expected) cerr << "error" << FAIL;
+		queries++;
+	}
+	cerr << "tested same: " << queries << endl;
+}
+
+void stress_parallel(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto [a, b] = Random::line(range);
+		auto [c, d] = Random::line(range);
+
+		line lAB = pointsToLine(a, b);
+		line lCD = pointsToLine(c, d);
+
+		auto got = parallel(lAB, lCD);
+		auto expected = cross(b-a, d-c) == 0;
+
+		if (got != expected) cerr << "error" << FAIL;
+		queries++;
+	}
+	cerr << "tested parallel: " << queries << endl;
+}
+
+void stress_intersect(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto [a, b] = Random::line(range);
+		auto [c, d] = Random::line(range);
+
+		line lAB = pointsToLine(a, b);
+		line lCD = pointsToLine(c, d);
+
+		if (same(lAB, lCD)) continue;
+
+		pt gotPT;
+		auto got = intersect(lAB, lCD, gotPT);
+		auto expected = lineIntersection(a, b, c, d);
+
+		if (got != expected) cerr << "error: 1" << FAIL;
+		if (got) {
+			pt expectedPt = lineIntersection2(a, b, c, d);
+			if (float_error(real(gotPT), real(expectedPt)) > 1e-6) cerr << "error: 2" << FAIL;
+			if (float_error(imag(gotPT), imag(expectedPt)) > 1e-6) cerr << "error: 2" << FAIL;
+		}
+		queries++;
+	}
+	cerr << "tested intersect: " << queries << endl;
+}
+
+int main() {
+	stress_pointsToLine(100);
+	stress_pointsToLine(100'000);
+	stress_same(10);
+	stress_same(100);
+	stress_same(1'000'000'000);//no precision issue since this will alwas be false...
+	stress_parallel(10);
+	stress_parallel(100);
+	stress_parallel(1'000'000'000);
+	stress_intersect(100);
+	stress_intersect(1'000'000'000);
+}
diff --git a/test/geometry/linesAndSegments.cpp b/test/geometry/linesAndSegments.cpp
index 2943a67..a2da3ba 100644
--- a/test/geometry/linesAndSegments.cpp
+++ b/test/geometry/linesAndSegments.cpp
@@ -30,7 +30,7 @@ void stress_lineIntersection(ll range) {
 		auto [c, d] = Random::line(range);
 		if (ccw(a, b, c) == 0 && ccw(a, b, d) == 0) continue;
 
-		bool expected = ccw(0, a-b, c-d) == 0;
+		bool expected = ccw(0, a-b, c-d) != 0;
 		bool got = lineIntersection(a, b, c, d);
 
 		if (got != expected) cerr << "error" << FAIL;
@@ -49,7 +49,7 @@ void stress_lineIntersection2(ll range) {
 		auto got = lineIntersection2(a, b, c, d);
 
 		if (distToLine(a, b, got) > 1e-6) cerr << "error: 1" << FAIL;
-		if (distToLine(a, b, got) > 1e-6) cerr << "error: 2" << FAIL;
+		if (distToLine(c, d, got) > 1e-6) cerr << "error: 2" << FAIL;
 		queries++;
 	}
 	cerr << "tested lineIntersection2: " << queries << endl;
@@ -172,7 +172,7 @@ void stress_segmentIntersection2(ll range) {
 		if (!got.empty() != tmp) cerr << "error: 1" << FAIL;
 		for (pt p : got) {
 			if (distToSegment(a, b, p) > 1e-6) cerr << "error: 2" << FAIL;
-			if (distToSegment(a, b, p) > 1e-6) cerr << "error: 3" << FAIL;
+			if (distToSegment(c, d, p) > 1e-6) cerr << "error: 3" << FAIL;
 		}
 		if (tmp) {
 			double gotDist = abs(got.front() - got.back());
@@ -220,7 +220,7 @@ int main() {
 	stress_lineIntersection(100);
 	stress_lineIntersection(1'000'000'000);
 	stress_lineIntersection2(100);
-	stress_lineIntersection2(1'000'000);
+	stress_lineIntersection2(1'000);//intersection can bet at N^3...
 	stress_distToLine(100);
 	stress_distToLine(1'000'000'000);
 	stress_projectToLine(100);
diff --git a/test/geometry/polygon.cpp b/test/geometry/polygon.cpp
index 1dd46ca..643ea70 100644
--- a/test/geometry/polygon.cpp
+++ b/test/geometry/polygon.cpp
@@ -10,7 +10,7 @@ double abs(pt p) {
 	return hypot(real(p), imag(p));
 }
 // Liegt p auf der Strecke a-b?
-bool pointOnLineSegment(pt a, pt b, pt p) {
+bool pointOnSegment(pt a, pt b, pt p) {
 	if (cross(a, b, p) != 0) return false;
 	auto dist = norm(a - b);
 	return norm(a - p) <= dist && norm(b - p) <= dist;
@@ -65,7 +65,7 @@ void test_windingNumber(ll range) {
 				int cur = details::lineSegmentIntersection(p, p + pt(1, 2'000'000'007), ps[j], ps[j+1]);
 				if (ptLess(ps[j], ps[j+1])) expected -= cur;
 				else expected += cur;
-				onBorder |= pointOnLineSegment(ps[j], ps[j+1], p);
+				onBorder |= pointOnSegment(ps[j], ps[j+1], p);
 			}
 			if (onBorder) continue;
 			if (area(ps) < 0) expected = -expected;
@@ -93,7 +93,7 @@ void test_inside(ll range) {
 			bool onBorder = false;
 			for (int j = 0; j < n; j++) {
 				count += details::lineSegmentIntersection(p, p + pt(1, 2'000'000'007), ps[j], ps[j+1]);
-				onBorder |= pointOnLineSegment(ps[j], ps[j+1], p);
+				onBorder |= pointOnSegment(ps[j], ps[j+1], p);
 			}
 			bool expected = (count % 2) && !onBorder;
 			bool got = inside(p, ps);
diff --git a/test/geometry/segmentIntersection.cpp b/test/geometry/segmentIntersection.cpp
index 9862be5..6d3ddd6 100644
--- a/test/geometry/segmentIntersection.cpp
+++ b/test/geometry/segmentIntersection.cpp
@@ -14,7 +14,7 @@ bool pointOnLineSegment(pt a, pt b, pt p) {
 }
 
 // Test auf Streckenschnitt zwischen a-b und c-d.
-bool lineSegmentIntersection(pt a, pt b, pt c, pt d) {
+bool segmentIntersection(pt a, pt b, pt c, pt d) {
 	if (ccw(a, b, c) == 0 && ccw(a, b, d) == 0)
 			return pointOnLineSegment(a,b,c) ||
 			       pointOnLineSegment(a,b,d) ||
@@ -42,7 +42,7 @@ vector<seg> randomSegs(int n, ll range) {
 bool naive(vector<seg>& segs) {
 	for (ll i = 0; i < sz(segs); i++) {
 		for (ll j = 0; j < i; j++) {
-			if (lineSegmentIntersection(segs[i].a, segs[i].b, segs[j].a, segs[j].b)) return true;
+			if (segmentIntersection(segs[i].a, segs[i].b, segs[j].a, segs[j].b)) return true;
 		}
 	}
 	return false;
@@ -60,7 +60,7 @@ void stress_test(ll range) {
 		if (got != (b >= 0)) cerr << "error: invalid ans" << FAIL;
 		auto expected = naive(segs);
 		if (got != expected) cerr << "error: intersection not found" << FAIL;
-		if (got && !lineSegmentIntersection(segs[a].a, segs[a].b, segs[b].a, segs[b].b)) cerr << "error: no intersection" << FAIL;
+		if (got && !segmentIntersection(segs[a].a, segs[a].b, segs[b].a, segs[b].b)) cerr << "error: no intersection" << FAIL;
 		queries += n;
 		intersection += got;
 		notIntersection += !got;
diff --git a/test/geometry/spheres.cpp b/test/geometry/spheres.cpp
new file mode 100644
index 0000000..16e0ebd
--- /dev/null
+++ b/test/geometry/spheres.cpp
@@ -0,0 +1,28 @@
+#include "../util.h"
+constexpr double PI = acos(-1.0);
+#pragma GCC diagnostic ignored "-Wshadow"
+#include <geometry/spheres.cpp>
+
+void test_consistent() {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		auto pLat = Random::real<double>(-180, 180);
+		auto pLon = Random::real<double>(0, 360);
+		auto qLat = Random::real<double>(-180, 180);
+		auto qLon = Random::real<double>(0, 360);
+
+		point p(pLat, pLon);
+		point q(qLat, qLon);
+
+		auto gotA = gcDist(pLat, pLon, qLat, qLon, 1);
+		auto gotB = gcDist(p, q);
+
+		if (abs(gotA - gotB) > 1e-6) cerr << "gotA: " << gotA << ", gotB: " << gotB << FAIL;
+		queries++;
+	}
+	cerr << "tested random: " << queries << endl;
+}
+
+int main() {
+	test_consistent();
+}
diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp
new file mode 100644
index 0000000..bba8104
--- /dev/null
+++ b/test/graph/connect.cpp
@@ -0,0 +1,140 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include "connectMinLCT.h"
+constexpr ll INF = 0x3FFF'FFFF;
+#include <graph/connect.cpp>
+
+struct Naive {
+	vector<multiset<int>> adj;
+	vector<int> seen;
+	int counter;
+	Naive(int n) : adj(n), seen(n), counter(0) {}
+
+	template<typename F>
+	void dfs(int x, F&& f) {
+		counter++;
+		vector<int> todo = {x};
+		seen[x] = counter;
+		while (!todo.empty()) {
+			x = todo.back();
+			todo.pop_back();
+			f(x);
+			for (ll y : adj[x]) {
+				if (seen[y] != counter) {
+					seen[y] = counter;
+					todo.push_back(y);
+				}
+			}
+		}
+	}
+
+	bool connected(int a, int b) {
+		bool res = false;
+		dfs(a, [&](int x){res |= x == b;});
+		return res;
+	}
+
+	void addEdge(int a, int b) {
+		adj[a].insert(b);
+		adj[b].insert(a);
+	}
+
+	void eraseEdge(int a, int b) {
+		adj[a].erase(adj[a].find(b));
+		adj[b].erase(adj[b].find(a));
+	}
+};
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 2'000; tries++) {
+		int n = Random::integer<int>(2, 30);
+		int m = Random::integer<int>(30, 300);
+
+		vector<int> insertOrder(m);
+		iota(all(insertOrder), 0);
+		shuffle(all(insertOrder), Random::rng);
+		vector<pair<int, int>> edges(m, {-1, -1});
+
+		connect con(n, m);
+		Naive naive(n);
+
+		int deleted = 0;
+		for (int i = 0; i < m; i++) {
+			{
+				int a = Random::integer<int>(0, n);
+				int b = a;
+				while (b == a) b = Random::integer<int>(0, n);
+				edges[insertOrder[i]] = {a, b};
+
+				con.addEdge(a, b, insertOrder[i]);
+				naive.addEdge(a, b);
+			}
+
+			while (deleted < m && edges[deleted] != pair<int, int>{-1, -1} && Random::integer<int>(2) == 0) {
+				auto [a, b] = edges[deleted];
+
+				con.eraseEdge(deleted);
+				naive.eraseEdge(a, b);
+				deleted++;
+			}
+
+			for (int j = 0; j < n; j++) {
+				int a = Random::integer<int>(0, n);
+				int b = Random::integer<int>(0, n);
+
+				auto got = con.connected(a, b);
+				auto expected = naive.connected(a, b);
+
+				if (got != expected) cerr << "error" << FAIL;
+			}
+
+			queries += n;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 100'000;
+constexpr int M = 500'000;
+void performance_test() {
+	timer t;
+	t.start();
+	connect con(N, M);
+	t.stop();
+
+	vector<int> insertOrder(M);
+	iota(all(insertOrder), 0);
+	shuffle(all(insertOrder), Random::rng);
+	vector<bool> inserted(M);
+
+	for (int i = 0, j = 0; i < N; i++) {
+		int a = Random::integer<int>(0, N);
+		int b = a;
+		while (b == a) b = Random::integer<int>(0, N);
+		
+		t.start();
+		con.addEdge(a, b, insertOrder[i]);
+		t.stop();
+		inserted[i] = true;
+
+		while (j < M && inserted[j] && Random::integer<int>(2) == 0) {
+			t.start();
+			con.eraseEdge(j);
+			t.stop();
+		}
+	}
+	hash_t hash = 0;
+	for (int i = 1; i < N; i++) {
+		t.start();
+		hash += con.connected(i - 1, i);
+		t.stop();
+	}
+	if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/graph/connectMinLCT.h b/test/graph/connectMinLCT.h
new file mode 100644
index 0000000..4d509f7
--- /dev/null
+++ b/test/graph/connectMinLCT.h
@@ -0,0 +1,173 @@
+constexpr ll queryDefault = 0x3FFF'FFFF;
+constexpr ll updateDefault = 0;
+//modifiable:
+ll _modify(ll x, ll y) {
+	return min(x, y);
+}
+ll _query(ll x, ll y) {
+	return min(x, y);
+}
+ll _update(ll delta, int /*length*/) {
+	return delta;
+}
+
+//generic:
+ll joinValueDelta(ll value, ll delta) {
+	if (delta == updateDefault) return value;
+	return _modify(value, delta);
+}
+
+ll joinDeltas(ll delta1, ll delta2) {
+	if (delta1 == updateDefault) return delta2;
+	if (delta2 == updateDefault) return delta1;
+	return _modify(delta1, delta2);
+}
+
+struct LCT {
+	struct Node {
+		ll nodeValue, subTreeValue, delta;
+		bool revert;
+		int id, size;
+		Node *left, *right, *parent;
+
+		Node(int id = 0, int val = queryDefault) :
+			nodeValue(val), subTreeValue(val), delta(updateDefault),
+			revert(false), id(id), size(1),
+			left(nullptr), right(nullptr), parent(nullptr) {}
+
+		bool isRoot() {
+			return !parent || (parent->left != this &&
+			                   parent->right != this);
+		}
+
+		void push() {
+			if (revert) {
+				revert = false;
+				swap(left, right);
+				if (left) left->revert ^= 1;
+				if (right) right->revert ^= 1;
+			}
+			nodeValue = joinValueDelta(nodeValue, delta);
+			subTreeValue = joinValueDelta(subTreeValue,
+			                              _update(delta, size));
+			if (left) left->delta = joinDeltas(left->delta, delta);
+			if (right) right->delta = joinDeltas(right->delta, delta);
+			delta = updateDefault;
+		}
+
+		ll getSubtreeValue() {
+			return joinValueDelta(subTreeValue, _update(delta, size));
+		}
+
+		void update() {
+			subTreeValue = joinValueDelta(nodeValue, delta);
+			size = 1;
+			if (left) {
+				subTreeValue = _query(subTreeValue,
+				                      left->getSubtreeValue());
+				size += left->size;
+			}
+			if (right) {
+				subTreeValue = _query(subTreeValue,
+				                      right->getSubtreeValue());
+				size += right->size;
+		}}
+	};
+
+	vector<Node> nodes;
+
+	LCT(int n) : nodes(n) {
+		for (int i = 0; i < n; i++) nodes[i].id = i;
+	}
+
+	void connect(Node* ch, Node* p, int isLeftChild) {
+		if (ch) ch->parent = p;
+		if (isLeftChild >= 0) {
+			if (isLeftChild) p->left = ch;
+			else p->right = ch;
+	}}
+
+	void rotate(Node* x) {
+		Node* p = x->parent;
+		Node* g = p->parent;
+		bool isRootP = p->isRoot();
+		bool leftChildX = (x == p->left);
+
+		connect(leftChildX ? x->right : x->left, p, leftChildX);
+		connect(p, x, !leftChildX);
+		connect(x, g, isRootP ? -1 : p == g->left);
+		p->update();
+	}
+
+	void splay(Node* x) {
+		while (!x->isRoot()) {
+			Node* p = x->parent;
+			Node* g = p->parent;
+			if (!p->isRoot()) g->push();
+			p->push();
+			x->push();
+			if (!p->isRoot()) rotate((x == p->left) ==
+			                         (p == g->left) ?  p : x);
+			rotate(x);
+		}
+		x->push();
+		x->update();
+	}
+
+	Node* expose(Node* x) {
+		Node* last = nullptr;
+		for (Node* y = x; y; y = y->parent) {
+			splay(y);
+			y->left = last;
+			last = y;
+		}
+		splay(x);
+		return last;
+	}
+
+	void makeRoot(Node* x) {
+		expose(x);
+		x->revert ^= 1;
+	}
+
+	bool connected(Node* x, Node* y) {
+		if (x == y) return true;
+		expose(x);
+		expose(y);
+		return x->parent;
+	}
+
+	void link(Node* x, Node* y) {
+		assert(!connected(x, y)); // not yet connected!
+		makeRoot(x);
+		x->parent = y;
+	}
+
+	void cut(Node* x, Node* y) {
+		makeRoot(x);
+		expose(y);
+		//must be a tree edge!
+		assert(!(y->right != x || x->left != nullptr));
+		y->right->parent = nullptr;
+		y->right = nullptr;
+	}
+
+	Node* lca(Node* x, Node* y) {
+		assert(connected(x, y));
+		expose(x);
+		return expose(y);
+	}
+
+	ll query(Node* from, Node* to) {
+		makeRoot(from);
+		expose(to);
+		if (to) return to->getSubtreeValue();
+		return queryDefault;
+	}
+
+	void modify(Node* from, Node* to, ll delta) {
+		makeRoot(from);
+		expose(to);
+		to->delta = joinDeltas(to->delta, delta);
+	}
+};
diff --git a/test/graph/dinic.cpp b/test/graph/dinic.cpp
new file mode 100644
index 0000000..5af7c6f
--- /dev/null
+++ b/test/graph/dinic.cpp
@@ -0,0 +1,62 @@
+#include "../util.h"
+constexpr ll INF = LL::INF;
+namespace dinic {
+#include <graph/dinic.cpp>
+}
+
+namespace pushRelabel {
+#include <graph/pushRelabel.cpp>
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 20'000; tries++) {
+		int n = Random::integer<int>(2, 30);
+		int m = Random::integer<int>(n-1, max<int>(n, min<int>(500, n*(n-1) / 2 + 1)));
+
+		dinic::adj.assign(n, {});
+		pushRelabel::adj.assign(n, {});
+
+		Graph<NoData, true> g(n);
+		g.erdosRenyi(m);
+		g.forEdges([](int a, int b){
+			ll w = Random::integer<ll>(1, 1'000'000'000'000ll);
+			dinic::addEdge(a, b, w);
+			pushRelabel::addEdge(a, b, w);
+		});
+
+		ll got = dinic::maxFlow(0, n - 1);
+		ll expected = pushRelabel::maxFlow(0, n - 1);
+		
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 50000;
+constexpr int M = 200000;
+void performance_test() {
+	using namespace dinic;
+	timer t;
+	Graph<NoData> g(N);
+	g.erdosRenyi(M);
+	adj.assign(N, {});
+	g.forEdges([](int a, int b){
+		ll w1 = Random::integer<ll>(1, 1'000'000'000'000ll);
+		ll w2 = Random::integer<ll>(1, 1'000'000'000'000ll);
+		addEdge(a, b, w1);
+		addEdge(b, a, w2);
+	});
+
+	t.start();
+	hash_t hash = maxFlow(0, N - 1);
+	t.stop();
+	if (t.time > 2000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/graph/hld.cpp b/test/graph/hld.cpp
new file mode 100644
index 0000000..bcd9c8c
--- /dev/null
+++ b/test/graph/hld.cpp
@@ -0,0 +1,83 @@
+#include "../util.h"
+#include <graph/hld.cpp>
+
+struct Seg { // very real segment tree
+    vector<int> a;
+
+    Seg(int n) : a(n) {}
+    
+    void inc(int l, int r) {
+        for (int i=l; i<r; i++) a[i]++;
+    }
+};
+
+void stress_test() {
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 50);
+		Graph<NoData> g(n);
+		g.tree();
+
+        adj.assign(n, {});
+		g.forEdges([&](int a, int b){
+			adj[a].push_back(b);
+			adj[b].push_back(a);
+		});
+
+        init(Random::integer(0, n));
+
+        vector<int> a(n);
+        auto dfs = [&](auto& self, int u, int p, int t) {
+            if (u == t) {
+                a[u]++;
+                return true;
+            }
+            for (int v : adj[u]) if (v != p) {
+                if (self(self, v, u, t)) {
+                    a[u]++;
+                    return true;
+                }
+            }
+            return false;
+        };
+
+        Seg seg(n);
+
+        int Q = Random::integer(1, 50);
+        for (int q=0; q<Q; q++) {
+            int u = Random::integer(0, n), v = Random::integer(0, n);
+            for_intervals(u, v, [&](int l, int r) { seg.inc(l, r); });
+            dfs(dfs, u, -1, v);
+        }
+        for (int i=0; i<n; i++) {
+            if (seg.a[in[i]] != a[i]) cerr << "WA: expected " << a[i] << " got " << seg.a[in[i]] << FAIL;
+        }
+	}
+	cerr << "tested random tests: " << 100'000 << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	Graph<NoData> g(N);
+	g.tree();
+    adj.assign(N, {});
+	g.forEdges([&](int a, int b){
+		adj[a].push_back(b);
+		adj[b].push_back(a);
+	});
+    vector<pair<int, int>> qu(N);
+    for (auto& [x, y] : qu) x = Random::integer(0, N), y = Random::integer(0, N);
+
+    ll hash = 0;
+	t.start();
+    init(0);
+    for (auto [x, y] : qu) for_intervals(x, y, [&](int l, int r){ hash += r-l; });
+	t.stop();
+	if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+    performance_test();
+}
diff --git a/test/graph/reroot.cpp b/test/graph/reroot.cpp
new file mode 100644
index 0000000..d5043b4
--- /dev/null
+++ b/test/graph/reroot.cpp
@@ -0,0 +1,59 @@
+#include "../util.h"
+#include <graph/reroot.cpp>
+
+void stress_test() {
+	for (int tries = 0; tries < 50'000; tries++) {
+		int n = Random::integer<int>(1, 50);
+		Graph<NoData> g(n);
+		g.tree();
+
+        adj.assign(n, {});
+		g.forEdges([&](int a, int b){
+			adj[a].emplace_back(b, Random::integer(0, 10));
+			adj[b].emplace_back(a, Random::integer(0, 10));
+		});
+
+        Reroot re;
+        auto ans = re.solve();
+
+        auto dfs = [&](auto& self, int u, int p) -> ll {
+            ll val = 0;
+            for (auto [v, w] : adj[u]) if (v != p) {
+                val ^= ((v ^ u) + self(self, v, u)) * w % MOD;
+            }
+            return u ^ val;
+        };
+        for (int i=0; i<n; i++) {
+            if (ans[i] != dfs(dfs, i, -1)) {
+                cerr << "WA expected " << dfs(dfs, i, -1) << " got " << ans[i] << FAIL;
+            }
+        }
+	}
+	cerr << "tested random 50'000 tests" << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	Graph<NoData> g(N);
+	g.tree();
+    adj.assign(N, {});
+	g.forEdges([&](int a, int b){
+        adj[a].emplace_back(b, Random::integer(0, (int)1e9));
+        adj[b].emplace_back(a, Random::integer(0, (int)1e9));
+	});
+
+    ll hash = 0;
+	t.start();
+    Reroot re;
+    auto ans = re.solve();
+    hash = accumulate(all(ans), 0LL);
+	t.stop();
+	if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/graph/reroot.cpp.awk b/test/graph/reroot.cpp.awk
new file mode 100644
index 0000000..37ce8c3
--- /dev/null
+++ b/test/graph/reroot.cpp.awk
@@ -0,0 +1,7 @@
+BEGIN { print "constexpr ll MOD = 1e9 + 7;" }
+{ 
+    sub("W w, T x) {\\}", "W w, T x) { return ((v ^ c) + x) * w % MOD; }")
+    sub("T x, T y) {\\}", "T x, T y) { return x ^ y; }")
+    sub("int v, T x) {\\}", "int v, T x) { return v ^ x; }")
+}
+{ print }
diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp
index 123050f..9ab7051 100644
--- a/test/graph/scc.cpp
+++ b/test/graph/scc.cpp
@@ -16,18 +16,6 @@ void stress_test() {
 		});
 		scc();
 
-		vector<bool> tmp(n);
-		for (int i = 0; i < sz(sccs); i++) {
-			for (int x : sccs[i]) {
-				if (tmp[x]) cerr << "error: duclicate" << FAIL;
-				if (idx[x] != i) cerr << "error: inconsistent" << FAIL;
-				tmp[x] = true;
-			}
-		}
-		for (int i = 0; i < n; i++) {
-			if (!tmp[i]) cerr << "error: missing" << FAIL;
-		}
-
 		init(n);
 		vector<ll> seen(n);
 		int tmpCounter = 0;
diff --git a/test/graph/virtualTree.cpp b/test/graph/virtualTree.cpp
new file mode 100644
index 0000000..d256760
--- /dev/null
+++ b/test/graph/virtualTree.cpp
@@ -0,0 +1,95 @@
+#include "../util.h"
+int lca(int u, int v);
+#include <graph/virtualTree.cpp>
+
+vector<int> d, par;
+void dfs(int u, vector<vector<int>>& adj, int& counter) {
+    in[u] = counter++;
+    for (int v : adj[u]) if (v != par[u]) {
+        d[v] = d[u]+1;
+        par[v] = u;
+        dfs(v, adj, counter);
+    }
+    out[u] = counter;
+}
+
+int lca(int u, int v) {
+    if (d[u] < d[v]) swap(u, v);
+    while (d[u] > d[v]) u = par[u];
+    while (u != v) u = par[u], v = par[v];
+    return u;
+}
+
+void init(vector<vector<int>>& adj) {
+    int n = (int)sz(adj);
+    d.assign(n, 0);
+    in = par = out = d;
+    int counter = 0;
+    dfs(0, adj, counter);
+}
+
+void stress_test() {
+	for (int tries = 0; tries < 50'000; tries++) {
+		int n = Random::integer<int>(1, 50);
+		Graph<NoData> g(n);
+		g.tree();
+
+		vector<vector<int>> adj(n);
+		g.forEdges([&](int a, int b){
+			adj[a].push_back(b);
+			adj[b].push_back(a);
+		});
+
+        init(adj);
+        vector<int> ind = Random::distinct(Random::integer(1, n+1), 0, n);
+        auto [idk, tree] = virtualTree(ind);
+        vector<pair<int, int>> edges;
+        for (int i=0; i<sz(idk); i++) for (int v : tree[i]) {
+            edges.emplace_back(idk[i], idk[v]);
+        }
+
+        vector<pair<int, int>> edges2;
+        vector<bool> used(n);
+        for (int u : ind) for (int v : ind) used[lca(u, v)] = true;
+        auto dfs = [&](auto& self, int u, int p, int last) -> void {
+            if (used[u]) {
+                if (last != -1) edges2.emplace_back(last, u);
+                last = u;
+            }
+            for (int v : adj[u]) if (v != p) self(self, v, u, last);
+        };
+        dfs(dfs, 0, -1, -1);
+
+        sort(all(edges)), sort(all(edges2));
+        if (edges != edges2) cerr << "WA edge list does not match" << FAIL;
+	}
+	cerr << "tested random 50'000 tests" << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	Graph<NoData> g(N);
+	g.tree();
+	vector<vector<int>> adj(N);
+	g.forEdges([&](int a, int b){
+		adj[a].push_back(b);
+		adj[b].push_back(a);
+	});
+
+    init(adj);
+    vector<int> ind = Random::distinct(N/2, 0, N);
+
+    ll hash = 0;
+	t.start();
+    auto [idk, tree] = virtualTree(ind);
+    hash = accumulate(all(idk), 0LL);
+	t.stop();
+	if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/graph/virtualTree.cpp.awk b/test/graph/virtualTree.cpp.awk
new file mode 100644
index 0000000..fe4bc62
--- /dev/null
+++ b/test/graph/virtualTree.cpp.awk
@@ -0,0 +1,7 @@
+/\/\/ v/ { 
+    print "return {ind, tree};"
+}
+{
+    sub("void", "pair<vector<int>, vector<vector<int>>>")
+}
+{ print }
diff --git a/test/math/divSum.cpp b/test/math/divSum.cpp
new file mode 100644
index 0000000..1f82387
--- /dev/null
+++ b/test/math/divSum.cpp
@@ -0,0 +1,48 @@
+#include "../util.h"
+#include <math/divSum.cpp>
+
+ll naive(ll n, ll m, ll a, ll b){
+	ll ans = 0;
+	for(ll i = 0; i < n; i++){
+		ans += (a*i+b)/m;
+	}
+	return ans;
+}
+
+void stress_test() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(1, 100);
+		int a = Random::integer<int>(0, 100);
+		int b = Random::integer<int>(0, 100);
+		ll expected = naive(n, m, a, b);
+		ll got = divSum(n, m, a, b);
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll n = Random::integer<ll>(1, 1'000'000'000);
+		ll m = Random::integer<ll>(1, 1'000'000'000);
+		ll a = Random::integer<ll>(0, 1'000'000'000);
+		ll b = Random::integer<ll>(0, 1'000'000'000);
+		t.start();
+		hash += divSum(n, m, a, b);
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp
index 37bacce..6e4759d 100644
--- a/test/math/gauss.cpp
+++ b/test/math/gauss.cpp
@@ -14,7 +14,7 @@ vector<vector<double>> inverseMat(const vector<vector<double>>& m) {
 		mat[i].resize(2*n);
 		mat[i][n+i] = 1;
 	}
-	gauss(n);//the unique cetc. checks are not usefull since we dont solve an lgs...
+	gauss(n); //the unique cetc. checks are not usefull since we dont solve an lgs...
 	vector<vector<double>> res(m);
 	for (int i = 0; i < n; i++) {
 		res[i] = vector<double>(mat[i].begin() + n, mat[i].end());
diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp
index 85ab0d2..acdc555 100644
--- a/test/math/inversionsMerge.cpp
+++ b/test/math/inversionsMerge.cpp
@@ -16,7 +16,7 @@ void stress_test() {
 	for (ll i = 0; i < 100'000; i++) {
 		int n = Random::integer<int>(1, 100);
 		vector<ll> v(n);
-		for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000);//values must be unique ):
+		for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000); //values must be unique ):
 		shuffle(all(v), Random::rng);
 		ll expected = naive(v);
 		ll got = mergeSort(v);
diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp
index 21a8a7c..8640980 100644
--- a/test/math/linearRecurrence.cpp
+++ b/test/math/linearRecurrence.cpp
@@ -1,6 +1,11 @@
 #include "../util.h"
+vector<ll> mul(const vector<ll>& a, const vector<ll>& b);
 #include <math/linearRecurrence.cpp>
 
+vector<ll> mul(const vector<ll>& a, const vector<ll>& b) {
+	return mulSlow(a, b);
+}
+
 struct RandomRecurence {
 	vector<ll> f, c, cache;
 	RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
diff --git a/test/math/linearRecurrence.cpp.awk b/test/math/linearRecurrence.cpp.awk
new file mode 100644
index 0000000..902fd4b
--- /dev/null
+++ b/test/math/linearRecurrence.cpp.awk
@@ -0,0 +1,4 @@
+/vector<ll> mul/ { 
+    sub(/mul/, "mulSlow")
+}
+{ print }
diff --git a/test/math/linearRecurrenceNTT.cpp b/test/math/linearRecurrenceNTT.cpp
new file mode 100644
index 0000000..e03c27e
--- /dev/null
+++ b/test/math/linearRecurrenceNTT.cpp
@@ -0,0 +1,60 @@
+#include "../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/transforms/ntt.cpp>
+#include <math/transforms/multiplyNTT.cpp>
+#define mod mod2
+#include <math/linearRecurrence.cpp>
+#undef mod
+static_assert(mod == mod2);
+
+struct RandomRecurence {
+	vector<ll> f, c, cache;
+	RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
+
+	ll operator()(ll k){
+		while (sz(cache) <= k) {
+			ll cur = 0;
+			for (ll i = 0; i < sz(c); i++) {
+				cur += (c[i] * cache[sz(cache) - i - 1]) % mod;
+			}
+			cur %= mod;
+			cache.push_back(cur);
+		}
+		return cache[k];
+	}
+};
+
+void stress_test() {
+	int queries = 0;
+	for (int i = 0; i < 1'000; i++) {
+		int n = Random::integer<int>(1, 10);
+		RandomRecurence f(n);
+		for (int j = 0; j < 100; j++) {
+			ll k = Random::integer<ll>(0, 1000);
+
+			ll got = kthTerm(f.f, f.c, k);
+			ll expected = f(k);
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 100'000;
+void performance_test() {
+	timer t;
+	RandomRecurence f(N);
+	t.start();
+	hash_t hash = kthTerm(f.f, f.c, 1e18);
+	t.stop();
+	if (t.time > 8000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/linearRecurrenceOld.cpp b/test/math/linearRecurrenceOld.cpp
new file mode 100644
index 0000000..dab2256
--- /dev/null
+++ b/test/math/linearRecurrenceOld.cpp
@@ -0,0 +1,54 @@
+#include "../util.h"
+#include <math/linearRecurrenceOld.cpp>
+
+struct RandomRecurence {
+	vector<ll> f, c, cache;
+	RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {}
+
+	ll operator()(ll k){
+		while (sz(cache) <= k) {
+			ll cur = 0;
+			for (ll i = 0; i < sz(c); i++) {
+				cur += (c[i] * cache[sz(cache) - i - 1]) % mod;
+			}
+			cur %= mod;
+			cache.push_back(cur);
+		}
+		return cache[k];
+	}
+};
+
+void stress_test() {
+	int queries = 0;
+	for (int i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 10);
+		RandomRecurence f(n);
+		for (int j = 0; j < 100; j++) {
+			ll k = Random::integer<ll>(0, 1000);
+
+			ll got = kthTerm(f.f, f.c, k);
+			ll expected = f(k);
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000;
+void performance_test() {
+	timer t;
+	RandomRecurence f(N);
+	t.start();
+	hash_t hash = kthTerm(f.f, f.c, 1e18);
+	t.stop();
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/math/minMod.cpp b/test/math/minMod.cpp
new file mode 100644
index 0000000..e49da11
--- /dev/null
+++ b/test/math/minMod.cpp
@@ -0,0 +1,92 @@
+#include "../util.h"
+#include <math/shortModInv.cpp>
+#include <math/minMod.cpp>
+
+ll naiveMinMod(ll n, ll m, ll a, ll b){
+	ll ans = m;
+	for(ll i = 0; i < n; i++){
+		ans = min(ans, (a*i+b)%m);
+	}
+	return ans;
+}
+
+ll naiveFirstVal(ll a, ll m, ll l, ll r){
+	for(ll i = 0; i < m; i++){
+		ll v = a*i % m;
+		if(l <= v && v <= r) return v;
+	}
+	return -1;
+}
+
+void stress_test_minMod() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(1, 100);
+		int a = Random::integer<int>(0, m);
+		int b = Random::integer<int>(0, m);
+		ll expected = naiveMinMod(n, m, a, b);
+		ll got = minMod(n, m, a, b);
+		if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+void stress_test_firstVal() {
+	ll queries = 0;
+	for (ll i = 0; i < 10'000; i++) {
+		int m = Random::integer<int>(1, 100);
+		int a = Random::integer<int>(0, m);
+		int l = Random::integer<int>(0, m);
+		int r = Random::integer<int>(0, m);
+		if(l > r) swap(l, r);
+		ll expected = naiveFirstVal(a, m, l, r);
+		ll got = firstVal(a, m, l, r);
+		if (got != expected) cerr << a << " " << m << " " << l << " " << r << "got: " << got << ", expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test_minMod() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll n = Random::integer<ll>(1, 1'000'000'000);
+		ll m = Random::integer<ll>(1, 1'000'000'000);
+		ll a = Random::integer<ll>(0, m);
+		ll b = Random::integer<ll>(0, m);
+		t.start();
+		hash += minMod(n, m, a, b);
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+void performance_test_firstVal() {
+	timer t;
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll m = Random::integer<ll>(1, 1'000'000'000);
+		ll a = Random::integer<ll>(1, m);
+		ll l = Random::integer<ll>(0, m);
+		ll r = Random::integer<ll>(0, m);
+		if(l > r) swap(l, r);
+		t.start();
+		hash += firstVal(a, m, l, r);
+		t.stop();
+	}
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test_minMod();
+	stress_test_firstVal();
+	performance_test_minMod();
+	performance_test_firstVal();
+}
+
diff --git a/test/math/polynomial.cpp b/test/math/polynomial.cpp
new file mode 100644
index 0000000..f4a9486
--- /dev/null
+++ b/test/math/polynomial.cpp
@@ -0,0 +1,153 @@
+#include "../util.h"
+#include <math/shortModInv.cpp>
+constexpr ll mod = 1'394'633'899;
+#include <math/polynomial.cpp>
+
+poly randomPoly(int deg) {
+	poly p;
+	p.data = Random::integers<ll>(deg + 1, 0, mod);
+	return p;
+}
+
+ll eval(const vector<ll>& p, ll x) {
+	ll res = 0;
+	for (ll i = 0, j = 1; i < sz(p); i++, j = (j * x) % mod) {
+		res += j * p[i];
+		res %= mod;
+	}
+	return res;
+}
+
+void test_eval() {
+	int queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int deg = Random::integer<int>(1, 30);
+		vector<ll> tmp = Random::integers<ll>(deg + 1, 0, mod);
+		poly p(deg);
+		for (int i = 0; i <= deg; i++) p[i] = tmp[i];
+
+		for (int i = 0; i <= deg + 7; i++) {
+			ll x = Random::integer<ll>(0, mod);
+
+			ll got = p(x);
+			ll expected = eval(tmp, x);
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += deg + 1;
+	}
+	cerr << "tested eval: " << queries << endl;
+}
+
+void test_add() {
+	int queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+		int m = Random::integer<int>(1, 30);
+		auto a = randomPoly(n);
+		auto b = randomPoly(m);
+
+		auto c = a;
+		c += b;
+
+		if (sz(c) > sz(a) && sz(c) > sz(b)) cerr << "error: wrong degree" << FAIL;
+
+		for (int i = 0; i <= n + m + 7; i++) {
+			ll x = Random::integer<ll>(0, mod);
+
+			ll got = c(x);
+			ll expected = (a(x) + b(x)) % mod;
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += n + m;
+	}
+	cerr << "tested add: " << queries << endl;
+}
+
+void test_mul() {
+	int queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+		int m = Random::integer<int>(1, 30);
+		auto a = randomPoly(n);
+		auto b = randomPoly(m);
+
+		auto c = a * b;
+		if (sz(c) > sz(a) + sz(b) - 1) cerr << "error: wrong degree" << FAIL;
+
+		for (int i = 0; i <= n + m + 7; i++) {
+			ll x = Random::integer<ll>(0, mod);
+
+			ll got = c(x);
+			ll expected = (a(x) * b(x)) % mod;
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += n + m;
+	}
+	cerr << "tested mul: " << queries << endl;
+}
+
+void test_shift() {
+	int queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+		int m = Random::integer<int>(1, 30);
+		auto a = randomPoly(n);
+
+		auto b = a << m;
+		if (sz(b) > sz(a)) cerr << sz(a) << " " << sz(b) << endl;
+		if (sz(b) > sz(a)) cerr << "error: wrong degree" << FAIL;
+
+		for (int i = 0; i <= n + 7; i++) {
+			ll x = Random::integer<ll>(0, mod);
+
+			ll got = b(x);
+			ll expected = a((x + m) % mod);
+
+			if (got != expected) {
+				for (ll y : b.data) cerr << y << " ";
+				cerr << endl;
+			}
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += n;
+	}
+	cerr << "tested shift: " << queries << endl;
+}
+
+void test_divmod() {
+	int queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+		int m = Random::integer<int>(1, 30);
+		auto a = randomPoly(n);
+		auto b = randomPoly(m);
+
+		auto [div, rem] = a.divmod(b);
+		if (sz(rem) > sz(b)) cerr << "error: wrong degree (rem)" << FAIL;
+		if (sz(div) > 1 + max<ll>(0, sz(a) - sz(b))) cerr << "error: wrong degree (div)" << FAIL;
+
+		for (int i = 0; i <= n + m; i++) {
+			ll x = Random::integer<ll>(0, mod);
+			ll d = multInv(b(x), mod);
+
+			ll got = (div(x) + rem(x) * d) % mod;
+			ll expected = (a(x) * d) % mod;
+
+			if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+		}
+		queries += n + m;
+	}
+	cerr << "tested divmod: " << queries << endl;
+}
+	
+int main() {
+	test_eval();
+	test_add();
+	test_mul();
+	test_shift();
+	test_divmod();
+}
+
diff --git a/test/math/recover.cpp b/test/math/recover.cpp
new file mode 100644
index 0000000..6f89e5a
--- /dev/null
+++ b/test/math/recover.cpp
@@ -0,0 +1,44 @@
+#include "../util.h"
+#include <math/recover.cpp>
+#include <math/shortModInv.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	timer t;
+	for (int i = 0; i < 500; i++) {
+		ll p = Random::prime<ll>(10000);
+		for (ll j = 0; 2*j*j < p; j++) {
+			for (ll b = 1; 2*b*b < p; b++) {
+				if (gcd(j, b) != 1) continue;
+				for (ll a : {-j, j}) {
+					ll c = a * multInv(b, p);
+					
+					t.start();
+					auto [x, y] = recover(c, p);
+					t.stop();
+
+					if (a != x || b != y) cerr << "got: " << x << "/" << y << ", expected: " << a << "/" << b << FAIL;
+					queries++;
+				}
+			}
+		}
+		for (ll c = 0; c < p; c++) {
+			t.start();
+			auto [x, y] = recover(c, p);
+			t.stop();
+
+			if (y < 0) continue;
+			if (y == 0) cerr << "error: y=0" << FAIL;
+			ll got = (((x * multInv(y, p)) % p) + p) % p;
+			if (got != c) cerr << "got: " << got << ", expected: " << c << FAIL;
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms" << endl;
+}
+
+int main() {
+	stress_test();
+}
diff --git a/test/math/rho.cpp b/test/math/rho.cpp
index 5e4792a..941524b 100644
--- a/test/math/rho.cpp
+++ b/test/math/rho.cpp
@@ -96,17 +96,25 @@ void stress_test() {
 	cerr << "stress tested: " << t.time << "ms" << endl;
 }
 
-constexpr int N = 2'000;
+ll randomHard(ll lim) {
+	ll root2 = sqrt(lim);
+	ll root3 = cbrt(lim);
+	ll a = Random::prime<ll>(root2 / 2 - root3, root2 / 2 + root3);
+	ll b = Random::prime<ll>(lim / a - root3, lim / a);
+	return a * b;
+}
+
+constexpr int N = 200;
 void performance_test() {
 	timer t;
 	hash_t hash = 0;
 	for (int operations = 0; operations < N; operations++) {
-		ll x = Random::integer<ll>(1e18 / 2, 1e18);
+		ll x = randomHard(1e18);
 		t.start();
 		hash += factor(x).size();
 		t.stop();
 	}
-	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
 	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
 }
 
diff --git a/test/math/transforms/seriesOperations.cpp b/test/math/transforms/seriesOperations.cpp
new file mode 100644
index 0000000..ee30e00
--- /dev/null
+++ b/test/math/transforms/seriesOperations.cpp
@@ -0,0 +1,145 @@
+#include "../../util.h"
+#include <math/modPowIterativ.cpp>
+#include <math/transforms/ntt.cpp>
+#include <math/transforms/multiplyNTT.cpp>
+#pragma GCC diagnostic ignored "-Wunused-variable"
+#include <math/transforms/seriesOperations.cpp>
+
+namespace reference {//checked against yosupo
+	vector<ll> poly_inv(vector<ll> a, int n){
+		vector<ll> q = {powMod(a[0], mod-2, mod)};
+		for(int len = 1; len < n; len *= 2){
+			vector<ll> a2 = a, q2 = q;
+			a2.resize(2*len), q2.resize(2*len);
+			ntt(q2);
+			for(int j = 0; j < 2; j++){
+				ntt(a2);
+				for(int i = 0; i < 2*len; i++) a2[i] = a2[i] * q2[i] % mod;
+				ntt(a2, true);
+				for(int i = 0; i < len; i++) a2[i] = 0;
+			}
+			for(int i = len; i < min(n, 2*len); i++) q.push_back((mod - a2[i]) % mod);
+		}
+		return q;
+	}
+
+	vector<ll> poly_deriv(vector<ll> a){
+		for(int i = 0; i < sz(a)-1; i++)
+			a[i] = a[i+1] * (i+1) % mod;
+		a.pop_back();
+		return a;
+	}
+
+	vector<ll> poly_integr(vector<ll> a){
+		if(a.empty()) return {0};
+		a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod);
+		for(int i = sz(a)-2; i > 0; i--)
+			a[i] = a[i-1] * powMod(i, mod-2, mod) % mod;
+		a[0] = 0;
+		return a;
+	}
+
+	vector<ll> poly_log(vector<ll> a, int n){
+		a = mul(poly_deriv(a), poly_inv(a, n));
+		a.resize(n-1);
+		a = poly_integr(a);
+		return a;
+	}
+
+	vector<ll> poly_exp(vector<ll> a, int n){
+		vector<ll> q = {1};
+		for(int len = 1; len < n; len *= 2){
+			vector<ll> p = poly_log(q, 2*len);
+			for(int i = 0; i < 2*len; i++)
+				p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod;
+			vector<ll> q2 = q;
+			q2.resize(2*len);
+			ntt(p), ntt(q2);
+			for(int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod;
+			ntt(p, true);
+			for(int i = len; i < min(n, 2*len); i++) q.push_back(p[i]);
+		}
+		return q;
+	}
+}
+
+void test_inv() {
+	ll queries = 0;
+	for (ll i = 0; i < 50'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(1, 100);
+		vector<ll> a = Random::integers<ll>(n, 0, mod);
+
+		auto got = poly_inv(a, m);
+		auto expected = reference::poly_inv(a, m);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested inv: " << queries << endl;
+}
+
+void test_deriv() {
+	ll queries = 0;
+	for (ll i = 0; i < 50'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		vector<ll> a = Random::integers<ll>(n, 0, mod);
+
+		auto got = poly_deriv(a);
+		auto expected = reference::poly_deriv(a);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested deriv: " << queries << endl;
+}
+
+void test_integr() {
+	ll queries = 0;
+	for (ll i = 0; i < 50'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		vector<ll> a = Random::integers<ll>(n, 0, mod);
+
+		auto got = poly_deriv(a);
+		auto expected = reference::poly_deriv(a);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested integr: " << queries << endl;
+}
+
+void test_log() {
+	ll queries = 0;
+	for (ll i = 0; i < 50'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(1, 100);
+		vector<ll> a = Random::integers<ll>(n, 0, mod);
+
+		auto got = poly_log(a, m);
+		auto expected = reference::poly_log(a, m);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested log: " << queries << endl;
+}
+
+void test_exp() {
+	ll queries = 0;
+	for (ll i = 0; i < 50'000; i++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(1, 100);
+		vector<ll> a = Random::integers<ll>(n, 0, mod);
+
+		auto got = poly_exp(a, m);
+		auto expected = reference::poly_exp(a, m);
+		if (got != expected) cerr << "error" << FAIL;
+		queries += n;
+	}
+	cerr << "tested exp: " << queries << endl;
+}
+
+int main() {
+	test_inv();
+	test_deriv();
+	test_integr();
+	test_log();
+	test_exp();
+}
diff --git a/test/missing.ignore b/test/missing.ignore
index 0f6956f..c5f97bc 100644
--- a/test/missing.ignore
+++ b/test/missing.ignore
@@ -1,6 +1,4 @@
-datastructures/stlRope.cpp
-other/bitOps.cpp
-other/pbs.cpp
+datastructures/pbds.cpp
 other/pragmas.cpp
 other/stuff.cpp
 other/timed.cpp
diff --git a/test/other/bitOps.cpp b/test/other/bitOps.cpp
new file mode 100644
index 0000000..44f6297
--- /dev/null
+++ b/test/other/bitOps.cpp
@@ -0,0 +1,59 @@
+#include "../util.h"
+#include <other/bitOps.cpp>
+
+void test_subsets() {
+	int queries = 0;
+	for (int i = 0; i < 1000'000; i++) {
+		int mask = 0;
+		int limBits = Random::integer<int>(1, 15);
+		for (int j = 0; j < limBits; j++) {
+			mask |= 1 << Random::integer<int>(0, 31);
+		}
+
+		int expeced = 1 << __builtin_popcount(mask);
+		int last = -1;
+		int seen = 1;
+		subsets(mask, [&](int active){
+			if (active <= 0) cerr << "error active: " << active << FAIL;
+			if (last >= 0 && active >= last) cerr << "error active: " << active  << ", last: " << last << FAIL;
+			last = active;
+			seen++;
+		});
+		if (expeced != seen) cerr << "got: " << seen << ", expeced: " << expeced << FAIL;
+		queries++;
+	}
+	cerr << "tested subsets queries: " << queries << endl;
+}
+
+ll naive(ll x) {
+	vector<ll> bits;
+	for (ll i = 0; i < 64; i++) {
+		bits.push_back(x & 1);
+		x >>= 1;
+	}
+	reverse(all(bits));
+	next_permutation(all(bits));
+	reverse(all(bits));
+	x = 0;
+	for (ll i = 0, j = 1; i < 64; i++, j <<= 1) {
+		if (bits[i] != 0) x |= j;
+	}
+	return x;
+}
+
+void test_nextPerm() {
+	int queries = 0;
+	for (int i = 0; i < 1000'000; i++) {
+		ll x = 4;//Random::integer<ll>(1, LL::INF);
+		ll got = nextPerm(x);
+		ll expeced = naive(x);
+		if (got != expeced) cerr << x << ": got: " << got << ", expeced: " << expeced << FAIL;
+		queries++;
+	}
+	cerr << "tested nextPerm queries: " << queries << endl;
+}
+
+int main() {
+	test_subsets();
+	test_nextPerm();
+}
\ No newline at end of file
diff --git a/test/other/bitOps.cpp.awk b/test/other/bitOps.cpp.awk
new file mode 100644
index 0000000..f1abcfb
--- /dev/null
+++ b/test/other/bitOps.cpp.awk
@@ -0,0 +1,9 @@
+/for \(int subset/ {
+	print "template<typename F>"
+	print "void subsets(int bitmask, F&& f) {"
+}
+/\/\/ Nächste Permutation/ {
+	print "	{f(subset);}"
+	print "}"
+}
+{ print }
diff --git a/test/other/divideAndConquer.cpp b/test/other/divideAndConquer.cpp
index a6fda9d..6d1b444 100644
--- a/test/other/divideAndConquer.cpp
+++ b/test/other/divideAndConquer.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll INF = LL::INF;
 #include <other/divideAndConquer.cpp>
 
 vector<vector<ll>> gen(int n) {
@@ -43,7 +43,7 @@ vector<vector<ll>> genQuick(int n) {
 }
 
 /*ll naive(int n, int m) {
-	vector<vector<ll>> state(m+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(m+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
 	for (int i = 1; i <= m; i++) {
 		for (int j = 1; j <= n; j++) {
@@ -56,9 +56,9 @@ vector<vector<ll>> genQuick(int n) {
 }*/
 
 vector<ll> naive(int n) {
-	vector<vector<ll>> state(n+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(n+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
-	vector<ll> res(n+1, inf);
+	vector<ll> res(n+1, INF);
 	for (int i = 1; i <= n; i++) {
 		for (int j = 1; j <= n; j++) {
 			for (int k = 1; k <= j; k++) {
diff --git a/test/other/fastSubsetSum.cpp b/test/other/fastSubsetSum.cpp
new file mode 100644
index 0000000..c61b1ea
--- /dev/null
+++ b/test/other/fastSubsetSum.cpp
@@ -0,0 +1,49 @@
+#include "../util.h"
+#include <other/fastSubsetSum.cpp>
+
+int subsetSum(vector<int> w, int t){
+	vector<bool> dp(t+1);
+	dp[0] = true;
+	for(int x : w){
+		for(int i = t; i >= x; i--){
+			dp[i] = dp[i] || dp[i-x];
+		}
+	}
+	int ma = 0;
+	for(int i = 0; i <= t; i++){
+		if(dp[i]) ma = i;
+	}
+	return ma;
+}
+
+void stress_test() {
+	int queries = 0;
+	for (int test = 0; test < 10'000; test++) {
+		int n = Random::integer<int>(1, 20);
+		int t = Random::integer<int>(1, 500);
+		vector<int> w = Random::integers<int>(n, 0, 50);
+		int got = fastSubsetSum(w, t);
+		int expected = subsetSum(w, t);
+		if(got != expected) cerr << "got: " << got << " expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+void performance_test() {
+	timer t;
+	int n = 10'000, a = 10'000;
+	vector<int> w = Random::integers<int>(n, 0, a);
+	int target = 10'000'000;
+	t.start();
+	hash_t hash = fastSubsetSum(w, target);
+	t.stop();
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
diff --git a/test/other/josephus2.cpp b/test/other/josephus2.cpp
index d28fe0d..85a9d28 100644
--- a/test/other/josephus2.cpp
+++ b/test/other/josephus2.cpp
@@ -31,7 +31,7 @@ void performance_test() {
 		hash += rotateLeft(1'000'000'000'000'000'000ll + i);
 	}
 	t.stop();
-	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
 	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
 }
 
diff --git a/test/other/knuth.cpp b/test/other/knuth.cpp
index d469ceb..aaf5059 100644
--- a/test/other/knuth.cpp
+++ b/test/other/knuth.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll INF = LL::INF;
 #include <other/knuth.cpp>
 
 vector<vector<ll>> gen(int n) {
@@ -43,7 +43,7 @@ vector<vector<ll>> genQuick(int n) {
 }
 
 /*ll naive(int n, int m, const vector<vector<ll>>& C) {
-	vector<vector<ll>> state(m+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(m+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
 	for (int i = 1; i <= m; i++) {
 		for (int j = 1; j <= n; j++) {
@@ -56,9 +56,9 @@ vector<vector<ll>> genQuick(int n) {
 }*/
 
 vector<ll> naive(int n, const vector<vector<ll>>& C) {
-	vector<vector<ll>> state(n+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(n+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
-	vector<ll> res(n+1, inf);
+	vector<ll> res(n+1, INF);
 	for (int i = 1; i <= n; i++) {
 		for (int j = 1; j <= n; j++) {
 			for (int k = 1; k <= j; k++) {
diff --git a/test/other/pbs.cpp b/test/other/pbs.cpp
new file mode 100644
index 0000000..ba3b9d0
--- /dev/null
+++ b/test/other/pbs.cpp
@@ -0,0 +1,103 @@
+#include "../util.h"
+
+struct Union {
+    vector<int> a;
+
+    Union(int n) : a(n, -1) {}
+
+    int find(int i) {
+        return a[i] < 0 ? i : a[i] = find(a[i]);
+    }
+
+    void join(int i, int j) {
+        i = find(i), j = find(j);
+        if (i == j) return;
+        a[j] = i;
+    }
+
+    bool same(int i, int j) {
+        return find(i) == find(j);
+    }
+};
+
+int n;
+Union un(0);
+void reset() {
+    un = Union(n);
+}
+
+vector<pair<int, int>> edges;
+void do_step(int i) {
+    auto [u, v] = edges[i];
+    un.join(u, v);
+}
+
+vector<pair<int, int>> queries;
+bool test(int i) {
+    auto [u, v] = queries[i];
+    return un.same(u, v);
+}
+
+#include <other/pbs.cpp>
+void stress_test() {
+	for (int it = 0; it < 100'000; it++) {
+        n = Random::integer(2, 31);
+        int Q = Random::integer(2, 31);
+        int MAX_OPERATIONS = n-1;
+
+        edges.clear();
+        for (int i=1; i<n; i++) {
+            edges.emplace_back(Random::integer(0, i), i);
+        }
+        shuffle(all(edges), Random::rng);
+        queries.clear();
+        for (int i=0; i<Q; i++) {
+            auto x = Random::distinct(2, n);
+            queries.emplace_back(x[0], x[1]);
+        }
+        vector<int> ans = pbs(Q, MAX_OPERATIONS);
+
+        vector<int> correct(Q, -1);
+        Union un2(n);
+        for (int j=0; j<MAX_OPERATIONS; j++) {
+            un2.join(edges[j].first, edges[j].second);
+            for (int k=0; k<Q; k++) if (correct[k] == -1) {
+                if (un2.same(queries[k].first, queries[k].second)) {
+                    correct[k] = j;
+                }
+            }
+        }
+
+        if (ans != correct) cerr << "Failed stress test" << FAIL;
+	}
+}
+
+void performance_test() {
+    n = 300'000;
+    constexpr int Q = 300'000;
+    int MAX_OPERATIONS = n-1;
+    edges.clear();
+    for (int i=1; i<n; i++) {
+        edges.emplace_back(Random::integer(0, i), i);
+    }
+    shuffle(all(edges), Random::rng);
+    queries.clear();
+    for (int i=0; i<Q; i++) {
+        auto x = Random::distinct(2, n);
+        queries.emplace_back(x[0], x[1]);
+    }
+
+    timer t;
+    t.start();
+    vector<int> ans = pbs(Q, MAX_OPERATIONS);
+    t.stop();
+    ll hash = accumulate(all(ans), 0LL);
+
+	if (t.time > 700) cerr << "too slow: " << t.time << FAIL;
+    cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+    stress_test();
+    performance_test();
+}
diff --git a/test/other/pbs.cpp.awk b/test/other/pbs.cpp.awk
new file mode 100644
index 0000000..3084ebd
--- /dev/null
+++ b/test/other/pbs.cpp.awk
@@ -0,0 +1,8 @@
+BEGIN { print "vector<int> pbs(int Q, int MAX_OPERATIONS) {" }
+{ 
+    sub(/\/\* requirement already fulfilled \*\//, "test(i)")
+    sub(/\/\/ simulation step/, "do_step(step);")
+    sub(/\/\/ reset simulation/, "reset();")
+}
+{ print }
+END { print "return high; }" }
diff --git a/test/util.h b/test/util.h
index ac0ea74..e123fc2 100644
--- a/test/util.h
+++ b/test/util.h
@@ -24,7 +24,11 @@ namespace details {
 }
 
 namespace Random {
-	mt19937_64 rng(3141592653589793238ll);
+	#ifdef SEED
+		mt19937_64 rng(SEED);
+	#else
+		mt19937_64 rng(3141592653589793238ll);
+	#endif
 	template<typename T = ll>
 	T integer(T l, T r) {
 		return uniform_int_distribution<T>(l, r-1)(rng);
@@ -182,7 +186,7 @@ namespace detail {
 		double t =
 		  chrono::duration_cast<chrono::duration<double, milli>>(end - start)
 		    .count();
-		return 50/t;
+		return 30/t;
 	}
 
 	double speed = benchmark();