merge mzuenni changes

53 files changed, 2889 insertions, 54 deletions

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();