XOR 基底

math/xor_basis.hpp · GitHub で見る

共通ページ

#include "lib/math/xor_basis.hpp"

XorBasis<> basis{3, 5};
auto maximum = basis.max_xor();
auto third = basis.kth(2);
auto coefficients = basis.coordinates(6);
auto perpendicular = basis.orthogonal_complement();

XorBasisWithWitness<> witness;
witness.insert(3);
witness.insert(5);
auto indices = witness.represent(6);

XorBasis<UInt = uint64_t, Bits = numeric_limits<UInt>::digits> は XOR で張られる空間を扱います。UInt は 64 bit 以下の符号なし整数型で、bool は除きます。1 <= Bits <= UInt のビット数 とし、挿入値は下位 Bits bit に収めます。既定では 64 bit 全てを使います。

以下で \(S\) は現在の空間、\(S_x=\{x\mathbin{\mathrm{xor}}s\mid s\in S\}\) です。空集合の XOR は 0 とし、重複する値は一つに数えます。empty() が真でも \(S=\{0\}\) です。

操作・型	内容・返り値	計算量
`XorBasis()`	零空間を構築	\(O(B)\)
`XorBasis{a,b,...}` / `XorBasis(vector<UInt>)`	与えた値で空間を構築	\(O(B+nB)\)
`value_type` / `count_type` / `bits`	`UInt`／`__uint128_t`／`Bits`	—（型・定数）
`rank()` / `empty()`	次元／次元が 0 か	\(O(1)\)
`count()`	\(S\) の異なる値の個数。\(2^{\mathrm{rank}}\)	\(O(1)\)
`clear()`	零空間に戻す	\(O(B)\)
`insert(value)`	値を追加。次元が増えたときのみ `true`	\(O(r)\)
`contains(value)`	\(S\) に含まれるか	\(O(r)\)
`reduce(value)`	同じ剰余類の最小代表。`min_xor(value)` と同じ	\(O(r)\)
`min_xor(x = 0)` / `max_xor(x = 0)`	\(S_x\) の最小値／最大値	\(O(r)\)
`min_nonzero()`	\(S\) の最小の非零値。存在しなければ `nullopt`	\(O(r)\)
`mex(x = 0)`	\(S_x\) に含まれない最小の非負整数。`count_type`	\(O(B)\)
`vectors()`	現在の独立な基底を `vector<UInt>` で返す	\(O(r)\)
`vectors_view()`	同じ基底を `span<const UInt>` で返す。空の基底なら空の view	\(O(1)\)
`canonical()`	同じ空間の一意な簡約基底を持つ `XorBasis` を返す。`vectors()` は昇順	\(O(B^2)\)
`coordinates(value)`	`vectors()` の何番目を XOR するかをビットで表す。作れなければ `nullopt`	\(O(r)\)
`combine(coefficients)`	`coordinates` の逆。`rank()` 以上のビットは 0 とする	\(O(r)\)
`kth(k,x = 0)`	\(S_x\) の昇順で 0 始まり `k` 番目。範囲外なら `nullopt`	\(O(B)\)
`count_less(value,x = 0)` / `count_leq(value,x = 0)`	\(S_x\) のうち、`value` 未満／以下の個数	\(O(B)\)
`count_range(lower,upper,x = 0)`	\(S_x\) のうち半開区間 `[lower,upper)` に入る個数。`lower <= upper`	\(O(B)\)
`index_of(value,x = 0)`	\(S_x\) での昇順の添字。含まれなければ `nullopt`	\(O(B)\)
`lower_bound(value,x = 0)` / `upper_bound(value,x = 0)`	\(S_x\) で `value` 以上／より大きい最小値。なければ `nullopt`	\(O(B)\)
`predecessor(value,x = 0)`	\(S_x\) で `value` 未満の最大値。なければ `nullopt`	\(O(B)\)
`merge(b)`	`b` との和空間に更新し、増えた次元数を返す	\(O(B^2)\)
`a \| b` / `a \|= b`	和空間／その代入	\(O(B^2)\)
`intersection(b)` / `a & b` / `a &= b`	共通部分の空間／その代入	\(O(B^2)\)
`intersection(values)`	生成列 `span<const UInt>` が張る空間との共通部分。`vector<UInt>` も渡せる	\(O(B+nB)\)
`is_subspace_of(b)`	`b` の部分空間か	\(O(B^2)\)
`a == b` / `a != b`	張る空間が同じか。挿入順は問わない	\(O(B^2)\)
`orthogonal_complement()`	下位 `Bits` bit の標準内積による直交補空間	\(O(B^2)\)

kth の添字、順序・個数クエリの境界値と返される個数・添字、mex は count_type を使います。64 次元の \(2^{64}\) 個も正確に扱えます。例えば全範囲の個数は count_range(0, __uint128_t(1) << 64) と書けます。UInt の最大値を超える境界値も利用できます。x は UInt の範囲で指定でき、Bits より上のビットはそのまま保持されます。

intersection(values) の生成列は従属な値・重複・0 を含んでいても構いません。n は生成列の要素数です。

vectors_view() は基底のコピーを作りません。返された view は元の XorBasis が生存し、変更されない間だけ使います。値の順序は vectors() と同じです。一時オブジェクトからは取得できません。

coordinates は元の入力の添字ではなく、現在の vectors() に対する係数です。元の入力による復元には次のクラスを使います。元の空間の任意の u と、直交補空間の任意の v に対して popcount(u & v) は偶数です。

XorBasisWithWitness<UInt,Bits> は、独立な入力の添字を保持します。テンプレート引数の既定値は XorBasis と同じです。

操作	内容・返り値	計算量
`XorBasisWithWitness()`	初期化	\(O(B)\)
`insert(value)`	値を追加。次元が増えたときのみ `true`	\(O(B)\)
`size()`	追加した回数。0 や従属な値も含む	\(O(1)\)
`basis()`	現在の `XorBasis` の const 参照。最大値・順序統計などのクエリに利用	\(O(1)\)
`represent(value)`	XOR が `value` になる元の入力の添字を `optional<vector<size_t>>` で返す	\(O(B)\)
`clear()`	基底と入力の添字を初期化	\(O(B)\)

添字は挿入順の 0 始まりで、返り値は昇順です。作れなければ nullopt、0 なら空の配列です。復元には高々 rank() 個の独立な入力を使います。

RollbackXorBasis<UInt,Bits> は挿入を巻き戻せます。

操作	内容	計算量
`RollbackXorBasis()`	初期化	\(O(B)\)
`insert(value)`	値を追加。次元が増えたときのみ `true`。従属でも履歴に残す	償却 \(O(B)\)
`basis()`	現在の `XorBasis` の const 参照	\(O(1)\)
`snapshot()`	現在の履歴の長さを `size_t` で返す	\(O(1)\)
`undo()`	最後の挿入を 1 回取り消す。履歴が空のときは呼ばない	\(O(1)\)
`rollback(token)`	指定した履歴の長さまで巻き戻す	取り消す回数に比例
`clear()`	基底と履歴を初期化	\(O(B+履歴の長さ)\)

token は現在の履歴の先頭部分を指すものにします。巻き戻して捨てた履歴や clear() より前の履歴は復元できません。過去の基底自体を保持する場合は basis() をコピーします。

PrefixXorBasis<UInt,Bits> は右端を順に進める区間クエリに使います。追加済み列を \(a_0,\ldots,a_{n-1}\) とすると、対象は [lower,n) です。

操作	内容・返り値	計算量
`PrefixXorBasis()`	初期化	\(O(B)\)
`push_back(value)`	末尾に値を追加。列全体の次元が増えたときのみ `true`	\(O(B)\)
`size()`	追加した要素数	\(O(1)\)
`rank(lower = 0)`	`[lower,size())` の次元	\(O(B)\)
`basis(lower = 0)`	`[lower,size())` の `XorBasis` を返す	\(O(B)\)
`min_xor(lower = 0,x = 0)` / `max_xor(lower = 0,x = 0)`	区間内の部分集合の XOR と `x` の XOR の最小値／最大値	\(O(B)\)
`contains(lower,value)`	区間内の部分集合の XOR で `value` を作れるか	\(O(B)\)
`clear()`	列を初期化	\(O(B)\)

0 <= lower <= size() とします。過去の右端の状態は保存しません。任意の [l,r) のクエリは右端 r の昇順に処理し、r 個まで追加してから basis(l) などを使います。全 prefix の基底を保存せず、固定サイズの作業領域で処理できます。

\(B=\mathrm{Bits}\)、\(r=\mathrm{rank()}\) とします。通常基底の追加・所属・最小最大・係数変換は \(O(r)\)、順序統計・mex は \(O(B)\)、最小非零値と基底の列挙は \(O(r)\) です。正規化・結合・共通部分・直交補空間・空間の比較は \(O(B^2)\)、生成列との共通部分と入力数 \(n\) からの構築は \(O(B+nB)\)、コピー・clear と保存領域は \(O(B)\) です。rank・empty・count・vectors_view は \(O(1)\)。次元が \(B\) のときは追加・所属・最小最大・kth・個数クエリを \(O(1)\) で処理します。復元付き基底の追加・復元は \(O(B)\)、保存領域は \(O(B)\)。ロールバックの追加は償却 \(O(B)\)、undo は \(O(1)\)、rollback は取り消す回数に比例し、履歴の領域は挿入回数に比例します。prefix 用の追加・各区間クエリ・基底の抽出は \(O(B)\)、保存領域は \(O(B)\) です。

依存ライブラリ

XOR 基底の内部演算

検証コード

test/xor_basis_intersection.test.cpp

コード

#line 1 "math/xor_basis.hpp"

#line 1 "components/xor_basis_core.hpp"

#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>

namespace xor_basis_detail {
template <class UInt, bool maximum = false>
#if defined(__GNUC__) || defined(__clang__)
__attribute__((always_inline))
#endif
inline UInt reduce_rows(UInt x, const UInt *row, int count) {
	int i = 0;
	auto step = [&](UInt value) {
		if constexpr (maximum) x = std::max(x, UInt(x ^ value));
		else x = std::min(x, UInt(x ^ value));
	};
	for (; i + 4 <= count; i += 4) {
		step(row[i]); step(row[i + 1]); step(row[i + 2]); step(row[i + 3]);
	}
	for (; i < count; ++i) step(row[i]);
	return x;
}

template <class UInt, int Bits>
struct Core {
	static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt> && !std::is_same_v<UInt, bool>);
	static constexpr int digits = std::numeric_limits<UInt>::digits;
	static_assert(0 < Bits && Bits <= digits && digits <= 64);
	static constexpr UInt mask = UInt(UInt(~UInt(0)) >> (digits - Bits));
	std::array<UInt, Bits> row{};
	std::array<std::uint8_t, Bits> at{};
	int dimension = 0;
	static bool valid(UInt x) { return (x & mask) == x; }
	static int pivot(UInt x) { return int(std::bit_width(std::uint64_t(x))) - 1; }
	int insert(UInt x) {
		assert(valid(x));
		if (dimension == Bits) return -1;
		x = reduce_rows(x, row.data(), dimension);
		if (!x) return -1;
		row[dimension] = x; at[pivot(x)] = std::uint8_t(dimension + 1);
		return dimension++;
	}
	UInt minimize(UInt x) const {
		if (dimension == Bits) return UInt(x & UInt(~mask));
		x = reduce_rows(x, row.data(), dimension);
		return x;
	}
	UInt maximize(UInt x) const {
		if (dimension == Bits) return UInt(x | mask);
		x = reduce_rows<UInt, true>(x, row.data(), dimension);
		return x;
	}
};
}

#line 9 "math/xor_basis.hpp"
#include <cstddef>
#line 11 "math/xor_basis.hpp"
#include <initializer_list>
#line 13 "math/xor_basis.hpp"
#include <optional>
#include <span>
#include <utility>
#include <vector>

template <class UInt, int Bits> class RollbackXorBasis;
template <class UInt, int Bits> class PrefixXorBasis;
template <class UInt, int Bits> class XorBasisWithWitness;

template <class UInt = std::uint64_t, int Bits = std::numeric_limits<UInt>::digits>
class XorBasis {
	using Core = xor_basis_detail::Core<UInt, Bits>;
	Core core;
	friend class RollbackXorBasis<UInt, Bits>;
	friend class PrefixXorBasis<UInt, Bits>;
	friend class XorBasisWithWitness<UInt, Bits>;

XorBasis intersection_range(std::span<const UInt> values) const {
		XorBasis result;
		if (empty()) return result;
		if (rank() == Bits) { for (UInt value : values) result.insert(value); return result; }
		if constexpr (Bits <= 32) {
			std::array<std::uint64_t, Bits> work;
			int n = rank();
			for (int i = 0; i < n; ++i) work[i] = std::uint64_t(core.row[i]) << 32;
			for (UInt value : values) {
				assert(Core::valid(value));
				std::uint64_t x = (std::uint64_t(value) << 32) | value;
				x = xor_basis_detail::reduce_rows(x, work.data(), n);
				if (x >> 32) work[n++] = x;
				else result.insert(UInt(x));
			}
			return result;
		}
		std::array<UInt, Bits> row{};
		for (int i = 0; i < rank(); ++i) row[Core::pivot(core.row[i])] = core.row[i];
		std::array<UInt, Bits> source{};
		for (UInt value : values) {
			assert(Core::valid(value));
			UInt x = value, y = value;
			while (x) {
				int i = Core::pivot(x);
				if (!row[i]) { row[i] = x; source[i] = y; break; }
				x ^= row[i]; y ^= source[i];
			}
			if (!x) result.insert(y);
		}
		return result;
	}

public:
	using value_type = UInt;
	using count_type = __uint128_t;
	static constexpr int bits = Bits;
	XorBasis() = default;
	XorBasis(std::initializer_list<UInt> values) { for (UInt x : values) insert(x); }
	explicit XorBasis(const std::vector<UInt> &values) { for (UInt x : values) insert(x); }
	int rank() const { return core.dimension; }
	bool empty() const { return rank() == 0; }
	count_type count() const { return count_type(1) << rank(); }
	void clear() { core = Core{}; }
	bool insert(UInt x) { return core.insert(x) >= 0; }
	UInt reduce(UInt x) const { return core.minimize(x); }
	bool contains(UInt x) const { return reduce(x) == 0; }
	UInt min_xor(UInt x = 0) const { return core.minimize(x); }
	UInt max_xor(UInt x = 0) const { return core.maximize(x); }
	count_type mex(UInt x = 0) const {
		if (!contains(x)) return 0;
		if (rank() == Bits) return count_type(1) << Bits;
		for (int i = 0; i < Bits; ++i) if (!core.at[i]) return count_type(1) << i;
		return count_type(1) << Bits;
	}
	std::optional<UInt> min_nonzero() const {
		if (empty()) return std::nullopt;
		return *std::min_element(core.row.begin(), core.row.begin() + rank());
	}
	std::span<const UInt> vectors_view() const & { return {core.row.data(), std::size_t(rank())}; }
	std::span<const UInt> vectors_view() const && = delete;
	std::vector<UInt> vectors() const {
		return {core.row.begin(), core.row.begin() + rank()};
	}
	XorBasis canonical() const {
		XorBasis result = *this;
		std::sort(result.core.row.begin(), result.core.row.begin() + rank());
		result.core.at.fill(0);
		for (int i = 0; i < rank(); ++i) {
			int p = Core::pivot(result.core.row[i]);
			result.core.at[p] = std::uint8_t(i + 1);
			for (int j = i + 1; j < rank(); ++j)
				if ((result.core.row[j] >> p) & 1) result.core.row[j] ^= result.core.row[i];
		}
		return result;
	}
	std::optional<UInt> coordinates(UInt x) const {
		UInt result = 0;
		for (int i = 0; i < rank(); ++i) if (UInt(x ^ core.row[i]) < x) {
			x ^= core.row[i]; result |= UInt(UInt(1) << i);
		}
		if (x) return std::nullopt;
		return result;
	}
	UInt combine(UInt coefficients) const {
		UInt result = 0;
		for (int i = 0; i < rank(); ++i) {
			if (coefficients & 1) result ^= core.row[i];
			coefficients >>= 1;
		}
		assert(!coefficients);
		return result;
	}
	std::optional<UInt> kth(count_type k, UInt x = 0) const {
		if (k >= count()) return std::nullopt;
		if (rank() == Bits) return UInt((x & UInt(~Core::mask)) | UInt(k));
		int remaining = rank();
		for (int i = Bits - 1; i >= 0; --i) if (core.at[i]) {
			--remaining;
			if (((x >> i) & 1) != ((k >> remaining) & 1)) x ^= core.row[core.at[i] - 1];
		}
		return x;
	}
	count_type count_less(count_type value, UInt x = 0) const {
		if (value >= (count_type(1) << Core::digits)) return count();
		UInt bound = UInt(value);
		UInt high = UInt(x & UInt(~Core::mask)), bound_high = UInt(bound & UInt(~Core::mask));
		if (high != bound_high) return high < bound_high ? count() : 0;
		if (rank() == Bits) return UInt(bound & Core::mask);
		count_type result = 0;
		int remaining = rank();
		for (int i = Bits - 1; i >= 0; --i) {
			bool target = (bound >> i) & 1;
			if (core.at[i]) {
				--remaining;
				if (target) result += count_type(1) << remaining;
				if (bool((x >> i) & 1) != target) x ^= core.row[core.at[i] - 1];
			} else if (bool((x >> i) & 1) != target) return result + (target ? count_type(1) << remaining : 0);
		}
		return result;
	}
	count_type count_leq(count_type value, UInt x = 0) const {
		if (value >= std::numeric_limits<UInt>::max()) return count();
		return count_less(value + 1, x);
	}
	count_type count_range(count_type lower, count_type upper, UInt x = 0) const {
		assert(lower <= upper);
		return count_less(upper, x) - count_less(lower, x);
	}
	std::optional<count_type> index_of(count_type value, UInt x = 0) const {
		if (value > std::numeric_limits<UInt>::max() || !contains(UInt(UInt(value) ^ x))) return std::nullopt;
		return count_less(value, x);
	}
	std::optional<UInt> lower_bound(count_type value, UInt x = 0) const { return kth(count_less(value, x), x); }
	std::optional<UInt> upper_bound(count_type value, UInt x = 0) const { return kth(count_leq(value, x), x); }
	std::optional<UInt> predecessor(count_type value, UInt x = 0) const {
		count_type k = count_less(value, x);
		return k ? kth(k - 1, x) : std::nullopt;
	}
	int merge(const XorBasis &other) {
		int before = rank();
		if (this != &other) for (int i = 0; i < other.rank(); ++i) {
			insert(other.core.row[i]);
			if (rank() == Bits) break;
		}
		return rank() - before;
	}
	bool is_subspace_of(const XorBasis &other) const {
		if (rank() > other.rank()) return false;
		for (int i = 0; i < rank(); ++i) if (!other.contains(core.row[i])) return false;
		return true;
	}
	bool operator==(const XorBasis &other) const { return rank() == other.rank() && is_subspace_of(other); }
	XorBasis intersection(const XorBasis &other) const {
		if (core.dimension == Bits || this == &other) return other;
		if (other.core.dimension == Bits) return *this;
		if (rank() < other.rank()) return other.intersection(*this);
		return intersection_range({other.core.row.data(), std::size_t(other.rank())});
	}
	template <class Range>
	requires requires(const Range &values) { std::span<const UInt>(values); }
	XorBasis intersection(const Range &values) const { return intersection_range(std::span<const UInt>(values)); }

XorBasis orthogonal_complement() const {
		auto reduced = canonical();
		XorBasis result;
		for (int j = 0; j < Bits; ++j) if (!reduced.core.at[j]) {
			UInt x = UInt(UInt(1) << j);
			for (int i = 0; i < rank(); ++i) if ((reduced.core.row[i] >> j) & 1) x |= UInt(UInt(1) << Core::pivot(reduced.core.row[i]));
			result.insert(x);
		}
		return result;
	}
	XorBasis &operator|=(const XorBasis &other) { merge(other); return *this; }
	XorBasis &operator&=(const XorBasis &other) { return *this = intersection(other); }
	friend XorBasis operator|(XorBasis a, const XorBasis &b) { a.merge(b); return a; }
	friend XorBasis operator&(const XorBasis &a, const XorBasis &b) { return a.intersection(b); }
};

template <class UInt = std::uint64_t, int Bits = std::numeric_limits<UInt>::digits>
class RollbackXorBasis {
	XorBasis<UInt, Bits> current;
	std::vector<int> history;

public:
	const XorBasis<UInt, Bits> &basis() const { return current; }
	std::size_t snapshot() const { return history.size(); }
	bool insert(UInt x) {
		history.push_back(-1);
		int i = current.core.insert(x);
		history.back() = i;
		return i >= 0;
	}
	void undo() {
		assert(!history.empty());
		int i = history.back(); history.pop_back();
		if (i >= 0) {
			current.core.at[current.core.pivot(current.core.row[i])] = 0;
			current.core.row[i] = 0; --current.core.dimension;
		}
	}
	void rollback(std::size_t token) { assert(token <= history.size()); while (history.size() > token) undo(); }
	void clear() { current.clear(); history.clear(); }
};

template <class UInt = std::uint64_t, int Bits = std::numeric_limits<UInt>::digits>
class PrefixXorBasis {
	using Core = xor_basis_detail::Core<UInt, Bits>;
	std::array<UInt, Bits> row{};
	std::array<std::size_t, Bits> position{};
	std::size_t length = 0;

public:
	std::size_t size() const { return length; }
	void clear() { row.fill(0); position.fill(0); length = 0; }
	bool push_back(UInt x) {
		assert(Core::valid(x) && length < std::numeric_limits<std::size_t>::max());
		std::size_t p = ++length;
		while (x) {
			int i = Core::pivot(x);
			if (!row[i]) { row[i] = x; position[i] = p; return true; }
			if (position[i] < p) { std::swap(position[i], p); std::swap(row[i], x); }
			x ^= row[i];
		}
		return false;
	}
	XorBasis<UInt, Bits> basis(std::size_t lower = 0) const {
		assert(lower <= length);
		XorBasis<UInt, Bits> result;
		for (int i = Bits - 1; i >= 0; --i) if (position[i] > lower) {
			int k = result.core.dimension++;
			result.core.row[k] = row[i]; result.core.at[i] = std::uint8_t(k + 1);
		}
		return result;
	}
	int rank(std::size_t lower = 0) const {
		assert(lower <= length);
		int result = 0;
		for (std::size_t p : position) result += p > lower;
		return result;
	}
	UInt min_xor(std::size_t lower = 0, UInt x = 0) const {
		assert(lower <= length);
		for (int i = Bits - 1; i >= 0; --i) if (position[i] > lower) x = std::min(x, UInt(x ^ row[i]));
		return x;
	}
	UInt max_xor(std::size_t lower = 0, UInt x = 0) const {
		assert(lower <= length);
		for (int i = Bits - 1; i >= 0; --i) if (position[i] > lower) x = std::max(x, UInt(x ^ row[i]));
		return x;
	}
	bool contains(std::size_t lower, UInt x) const { return min_xor(lower, x) == 0; }
};

template <class UInt = std::uint64_t, int Bits = std::numeric_limits<UInt>::digits>
class XorBasisWithWitness {
	using Core = xor_basis_detail::Core<UInt, Bits>;
	XorBasis<UInt, Bits> current;
	std::array<UInt, Bits> source{};
	std::array<std::size_t, Bits> index{};
	std::size_t length = 0;

public:
	const XorBasis<UInt, Bits> &basis() const { return current; }
	std::size_t size() const { return length; }
	void clear() { current.clear(); source.fill(0); length = 0; }
	bool insert(UInt x) {
		assert(Core::valid(x) && length < std::numeric_limits<std::size_t>::max());
		std::size_t id = length++;
		if (current.rank() == Bits) return false;
		UInt mask = UInt(UInt(1) << current.rank());
		for (int i = 0; i < current.rank(); ++i) if (UInt(x ^ current.core.row[i]) < x) {
			x ^= current.core.row[i]; mask ^= source[i];
		}
		if (!x) return false;
		int k = current.core.dimension++;
		index[k] = id; source[k] = mask; current.core.row[k] = x;
		current.core.at[Core::pivot(x)] = std::uint8_t(k + 1);
		return true;
	}
	std::optional<std::vector<std::size_t>> represent(UInt x) const {
		if (!Core::valid(x)) return std::nullopt;
		UInt mask = 0;
		for (int i = 0; i < current.rank(); ++i) if (UInt(x ^ current.core.row[i]) < x) {
			x ^= current.core.row[i]; mask ^= source[i];
		}
		if (x) return std::nullopt;
		std::vector<std::size_t> result;
		while (mask) {
			int i = std::countr_zero(std::uint64_t(mask));
			result.push_back(index[i]); mask &= UInt(mask - 1);
		}
		return result;
	}
};

#ifndef XOR_BASIS_HPP
#define XOR_BASIS_HPP

#include "../components/xor_basis_core.hpp"
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <limits>
#include <optional>
#include <span>
#include <utility>
#include <vector>

template <class UInt, int Bits> class RollbackXorBasis;
template <class UInt, int Bits> class PrefixXorBasis;
template <class UInt, int Bits> class XorBasisWithWitness;

template <class UInt = std::uint64_t, int Bits = std::numeric_limits<UInt>::digits>
class XorBasis {
	using Core = xor_basis_detail::Core<UInt, Bits>;
	Core core;
	friend class RollbackXorBasis<UInt, Bits>;
	friend class PrefixXorBasis<UInt, Bits>;
	friend class XorBasisWithWitness<UInt, Bits>;

	XorBasis intersection_range(std::span<const UInt> values) const {
		XorBasis result;
		if (empty()) return result;
		if (rank() == Bits) { for (UInt value : values) result.insert(value); return result; }
		if constexpr (Bits <= 32) {
			std::array<std::uint64_t, Bits> work;
			int n = rank();
			for (int i = 0; i < n; ++i) work[i] = std::uint64_t(core.row[i]) << 32;
			for (UInt value : values) {
				assert(Core::valid(value));
				std::uint64_t x = (std::uint64_t(value) << 32) | value;
				x = xor_basis_detail::reduce_rows(x, work.data(), n);
				if (x >> 32) work[n++] = x;
				else result.insert(UInt(x));
			}
			return result;
		}
		std::array<UInt, Bits> row{};
		for (int i = 0; i < rank(); ++i) row[Core::pivot(core.row[i])] = core.row[i];
		std::array<UInt, Bits> source{};
		for (UInt value : values) {
			assert(Core::valid(value));
			UInt x = value, y = value;
			while (x) {
				int i = Core::pivot(x);
				if (!row[i]) { row[i] = x; source[i] = y; break; }
				x ^= row[i]; y ^= source[i];
			}
			if (!x) result.insert(y);
		}
		return result;
	}

  public:
	using value_type = UInt;
	using count_type = __uint128_t;
	static constexpr int bits = Bits;
	XorBasis() = default;
	XorBasis(std::initializer_list<UInt> values) { for (UInt x : values) insert(x); }
	explicit XorBasis(const std::vector<UInt> &values) { for (UInt x : values) insert(x); }
	int rank() const { return core.dimension; }
	bool empty() const { return rank() == 0; }
	count_type count() const { return count_type(1) << rank(); }
	void clear() { core = Core{}; }
	bool insert(UInt x) { return core.insert(x) >= 0; }
	UInt reduce(UInt x) const { return core.minimize(x); }
	bool contains(UInt x) const { return reduce(x) == 0; }
	UInt min_xor(UInt x = 0) const { return core.minimize(x); }
	UInt max_xor(UInt x = 0) const { return core.maximize(x); }
	count_type mex(UInt x = 0) const {
		if (!contains(x)) return 0;
		if (rank() == Bits) return count_type(1) << Bits;
		for (int i = 0; i < Bits; ++i) if (!core.at[i]) return count_type(1) << i;
		return count_type(1) << Bits;
	}
	std::optional<UInt> min_nonzero() const {
		if (empty()) return std::nullopt;
		return *std::min_element(core.row.begin(), core.row.begin() + rank());
	}
	std::span<const UInt> vectors_view() const & { return {core.row.data(), std::size_t(rank())}; }
	std::span<const UInt> vectors_view() const && = delete;
	std::vector<UInt> vectors() const {
		return {core.row.begin(), core.row.begin() + rank()};
	}
	XorBasis canonical() const {
		XorBasis result = *this;
		std::sort(result.core.row.begin(), result.core.row.begin() + rank());
		result.core.at.fill(0);
		for (int i = 0; i < rank(); ++i) {
			int p = Core::pivot(result.core.row[i]);
			result.core.at[p] = std::uint8_t(i + 1);
			for (int j = i + 1; j < rank(); ++j)
				if ((result.core.row[j] >> p) & 1) result.core.row[j] ^= result.core.row[i];
		}
		return result;
	}
	std::optional<UInt> coordinates(UInt x) const {
		UInt result = 0;
		for (int i = 0; i < rank(); ++i) if (UInt(x ^ core.row[i]) < x) {
			x ^= core.row[i]; result |= UInt(UInt(1) << i);
		}
		if (x) return std::nullopt;
		return result;
	}
	UInt combine(UInt coefficients) const {
		UInt result = 0;
		for (int i = 0; i < rank(); ++i) {
			if (coefficients & 1) result ^= core.row[i];
			coefficients >>= 1;
		}
		assert(!coefficients);
		return result;
	}
	std::optional<UInt> kth(count_type k, UInt x = 0) const {
		if (k >= count()) return std::nullopt;
		if (rank() == Bits) return UInt((x & UInt(~Core::mask)) | UInt(k));
		int remaining = rank();
		for (int i = Bits - 1; i >= 0; --i) if (core.at[i]) {
			--remaining;
			if (((x >> i) & 1) != ((k >> remaining) & 1)) x ^= core.row[core.at[i] - 1];
		}
		return x;
	}
	count_type count_less(count_type value, UInt x = 0) const {
		if (value >= (count_type(1) << Core::digits)) return count();
		UInt bound = UInt(value);
		UInt high = UInt(x & UInt(~Core::mask)), bound_high = UInt(bound & UInt(~Core::mask));
		if (high != bound_high) return high < bound_high ? count() : 0;
		if (rank() == Bits) return UInt(bound & Core::mask);
		count_type result = 0;
		int remaining = rank();
		for (int i = Bits - 1; i >= 0; --i) {
			bool target = (bound >> i) & 1;
			if (core.at[i]) {
				--remaining;
				if (target) result += count_type(1) << remaining;
				if (bool((x >> i) & 1) != target) x ^= core.row[core.at[i] - 1];
			} else if (bool((x >> i) & 1) != target) return result + (target ? count_type(1) << remaining : 0);
		}
		return result;
	}
	count_type count_leq(count_type value, UInt x = 0) const {
		if (value >= std::numeric_limits<UInt>::max()) return count();
		return count_less(value + 1, x);
	}
	count_type count_range(count_type lower, count_type upper, UInt x = 0) const {
		assert(lower <= upper);
		return count_less(upper, x) - count_less(lower, x);
	}
	std::optional<count_type> index_of(count_type value, UInt x = 0) const {
		if (value > std::numeric_limits<UInt>::max() || !contains(UInt(UInt(value) ^ x))) return std::nullopt;
		return count_less(value, x);
	}
	std::optional<UInt> lower_bound(count_type value, UInt x = 0) const { return kth(count_less(value, x), x); }
	std::optional<UInt> upper_bound(count_type value, UInt x = 0) const { return kth(count_leq(value, x), x); }
	std::optional<UInt> predecessor(count_type value, UInt x = 0) const {
		count_type k = count_less(value, x);
		return k ? kth(k - 1, x) : std::nullopt;
	}
	int merge(const XorBasis &other) {
		int before = rank();
		if (this != &other) for (int i = 0; i < other.rank(); ++i) {
			insert(other.core.row[i]);
			if (rank() == Bits) break;
		}
		return rank() - before;
	}
	bool is_subspace_of(const XorBasis &other) const {
		if (rank() > other.rank()) return false;
		for (int i = 0; i < rank(); ++i) if (!other.contains(core.row[i])) return false;
		return true;
	}
	bool operator==(const XorBasis &other) const { return rank() == other.rank() && is_subspace_of(other); }
	XorBasis intersection(const XorBasis &other) const {
		if (core.dimension == Bits || this == &other) return other;
		if (other.core.dimension == Bits) return *this;
		if (rank() < other.rank()) return other.intersection(*this);
		return intersection_range({other.core.row.data(), std::size_t(other.rank())});
	}
	template <class Range>
	requires requires(const Range &values) { std::span<const UInt>(values); }
	XorBasis intersection(const Range &values) const { return intersection_range(std::span<const UInt>(values)); }

	XorBasis orthogonal_complement() const {
		auto reduced = canonical();
		XorBasis result;
		for (int j = 0; j < Bits; ++j) if (!reduced.core.at[j]) {
			UInt x = UInt(UInt(1) << j);
			for (int i = 0; i < rank(); ++i) if ((reduced.core.row[i] >> j) & 1) x |= UInt(UInt(1) << Core::pivot(reduced.core.row[i]));
			result.insert(x);
		}
		return result;
	}
	XorBasis &operator|=(const XorBasis &other) { merge(other); return *this; }
	XorBasis &operator&=(const XorBasis &other) { return *this = intersection(other); }
	friend XorBasis operator|(XorBasis a, const XorBasis &b) { a.merge(b); return a; }
	friend XorBasis operator&(const XorBasis &a, const XorBasis &b) { return a.intersection(b); }
};

template <class UInt = std::uint64_t, int Bits = std::numeric_limits<UInt>::digits>
class RollbackXorBasis {
	XorBasis<UInt, Bits> current;
	std::vector<int> history;

  public:
	const XorBasis<UInt, Bits> &basis() const { return current; }
	std::size_t snapshot() const { return history.size(); }
	bool insert(UInt x) {
		history.push_back(-1);
		int i = current.core.insert(x);
		history.back() = i;
		return i >= 0;
	}
	void undo() {
		assert(!history.empty());
		int i = history.back(); history.pop_back();
		if (i >= 0) {
			current.core.at[current.core.pivot(current.core.row[i])] = 0;
			current.core.row[i] = 0; --current.core.dimension;
		}
	}
	void rollback(std::size_t token) { assert(token <= history.size()); while (history.size() > token) undo(); }
	void clear() { current.clear(); history.clear(); }
};

template <class UInt = std::uint64_t, int Bits = std::numeric_limits<UInt>::digits>
class PrefixXorBasis {
	using Core = xor_basis_detail::Core<UInt, Bits>;
	std::array<UInt, Bits> row{};
	std::array<std::size_t, Bits> position{};
	std::size_t length = 0;

  public:
	std::size_t size() const { return length; }
	void clear() { row.fill(0); position.fill(0); length = 0; }
	bool push_back(UInt x) {
		assert(Core::valid(x) && length < std::numeric_limits<std::size_t>::max());
		std::size_t p = ++length;
		while (x) {
			int i = Core::pivot(x);
			if (!row[i]) { row[i] = x; position[i] = p; return true; }
			if (position[i] < p) { std::swap(position[i], p); std::swap(row[i], x); }
			x ^= row[i];
		}
		return false;
	}
	XorBasis<UInt, Bits> basis(std::size_t lower = 0) const {
		assert(lower <= length);
		XorBasis<UInt, Bits> result;
		for (int i = Bits - 1; i >= 0; --i) if (position[i] > lower) {
			int k = result.core.dimension++;
			result.core.row[k] = row[i]; result.core.at[i] = std::uint8_t(k + 1);
		}
		return result;
	}
	int rank(std::size_t lower = 0) const {
		assert(lower <= length);
		int result = 0;
		for (std::size_t p : position) result += p > lower;
		return result;
	}
	UInt min_xor(std::size_t lower = 0, UInt x = 0) const {
		assert(lower <= length);
		for (int i = Bits - 1; i >= 0; --i) if (position[i] > lower) x = std::min(x, UInt(x ^ row[i]));
		return x;
	}
	UInt max_xor(std::size_t lower = 0, UInt x = 0) const {
		assert(lower <= length);
		for (int i = Bits - 1; i >= 0; --i) if (position[i] > lower) x = std::max(x, UInt(x ^ row[i]));
		return x;
	}
	bool contains(std::size_t lower, UInt x) const { return min_xor(lower, x) == 0; }
};

template <class UInt = std::uint64_t, int Bits = std::numeric_limits<UInt>::digits>
class XorBasisWithWitness {
	using Core = xor_basis_detail::Core<UInt, Bits>;
	XorBasis<UInt, Bits> current;
	std::array<UInt, Bits> source{};
	std::array<std::size_t, Bits> index{};
	std::size_t length = 0;

  public:
	const XorBasis<UInt, Bits> &basis() const { return current; }
	std::size_t size() const { return length; }
	void clear() { current.clear(); source.fill(0); length = 0; }
	bool insert(UInt x) {
		assert(Core::valid(x) && length < std::numeric_limits<std::size_t>::max());
		std::size_t id = length++;
		if (current.rank() == Bits) return false;
		UInt mask = UInt(UInt(1) << current.rank());
		for (int i = 0; i < current.rank(); ++i) if (UInt(x ^ current.core.row[i]) < x) {
			x ^= current.core.row[i]; mask ^= source[i];
		}
		if (!x) return false;
		int k = current.core.dimension++;
		index[k] = id; source[k] = mask; current.core.row[k] = x;
		current.core.at[Core::pivot(x)] = std::uint8_t(k + 1);
		return true;
	}
	std::optional<std::vector<std::size_t>> represent(UInt x) const {
		if (!Core::valid(x)) return std::nullopt;
		UInt mask = 0;
		for (int i = 0; i < current.rank(); ++i) if (UInt(x ^ current.core.row[i]) < x) {
			x ^= current.core.row[i]; mask ^= source[i];
		}
		if (x) return std::nullopt;
		std::vector<std::size_t> result;
		while (mask) {
			int i = std::countr_zero(std::uint64_t(mask));
			result.push_back(index[i]); mask &= UInt(mask - 1);
		}
		return result;
	}
};

#endif

#line 1 "math/xor_basis.hpp"



#line 1 "components/xor_basis_core.hpp"



#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>

namespace xor_basis_detail {
template <class UInt, bool maximum = false>
#if defined(__GNUC__) || defined(__clang__)
__attribute__((always_inline))
#endif
inline UInt reduce_rows(UInt x, const UInt *row, int count) {
	int i = 0;
	auto step = [&](UInt value) {
		if constexpr (maximum) x = std::max(x, UInt(x ^ value));
		else x = std::min(x, UInt(x ^ value));
	};
	for (; i + 4 <= count; i += 4) {
		step(row[i]); step(row[i + 1]); step(row[i + 2]); step(row[i + 3]);
	}
	for (; i < count; ++i) step(row[i]);
	return x;
}

template <class UInt, int Bits>
struct Core {
	static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt> && !std::is_same_v<UInt, bool>);
	static constexpr int digits = std::numeric_limits<UInt>::digits;
	static_assert(0 < Bits && Bits <= digits && digits <= 64);
	static constexpr UInt mask = UInt(UInt(~UInt(0)) >> (digits - Bits));
	std::array<UInt, Bits> row{};
	std::array<std::uint8_t, Bits> at{};
	int dimension = 0;
	static bool valid(UInt x) { return (x & mask) == x; }
	static int pivot(UInt x) { return int(std::bit_width(std::uint64_t(x))) - 1; }
	int insert(UInt x) {
		assert(valid(x));
		if (dimension == Bits) return -1;
		x = reduce_rows(x, row.data(), dimension);
		if (!x) return -1;
		row[dimension] = x; at[pivot(x)] = std::uint8_t(dimension + 1);
		return dimension++;
	}
	UInt minimize(UInt x) const {
		if (dimension == Bits) return UInt(x & UInt(~mask));
		x = reduce_rows(x, row.data(), dimension);
		return x;
	}
	UInt maximize(UInt x) const {
		if (dimension == Bits) return UInt(x | mask);
		x = reduce_rows<UInt, true>(x, row.data(), dimension);
		return x;
	}
};
}


#line 9 "math/xor_basis.hpp"
#include <cstddef>
#line 11 "math/xor_basis.hpp"
#include <initializer_list>
#line 13 "math/xor_basis.hpp"
#include <optional>
#include <span>
#include <utility>
#include <vector>

template <class UInt, int Bits> class RollbackXorBasis;
template <class UInt, int Bits> class PrefixXorBasis;
template <class UInt, int Bits> class XorBasisWithWitness;

template <class UInt = std::uint64_t, int Bits = std::numeric_limits<UInt>::digits>
class XorBasis {
	using Core = xor_basis_detail::Core<UInt, Bits>;
	Core core;
	friend class RollbackXorBasis<UInt, Bits>;
	friend class PrefixXorBasis<UInt, Bits>;
	friend class XorBasisWithWitness<UInt, Bits>;

	XorBasis intersection_range(std::span<const UInt> values) const {
		XorBasis result;
		if (empty()) return result;
		if (rank() == Bits) { for (UInt value : values) result.insert(value); return result; }
		if constexpr (Bits <= 32) {
			std::array<std::uint64_t, Bits> work;
			int n = rank();
			for (int i = 0; i < n; ++i) work[i] = std::uint64_t(core.row[i]) << 32;
			for (UInt value : values) {
				assert(Core::valid(value));
				std::uint64_t x = (std::uint64_t(value) << 32) | value;
				x = xor_basis_detail::reduce_rows(x, work.data(), n);
				if (x >> 32) work[n++] = x;
				else result.insert(UInt(x));
			}
			return result;
		}
		std::array<UInt, Bits> row{};
		for (int i = 0; i < rank(); ++i) row[Core::pivot(core.row[i])] = core.row[i];
		std::array<UInt, Bits> source{};
		for (UInt value : values) {
			assert(Core::valid(value));
			UInt x = value, y = value;
			while (x) {
				int i = Core::pivot(x);
				if (!row[i]) { row[i] = x; source[i] = y; break; }
				x ^= row[i]; y ^= source[i];
			}
			if (!x) result.insert(y);
		}
		return result;
	}

  public:
	using value_type = UInt;
	using count_type = __uint128_t;
	static constexpr int bits = Bits;
	XorBasis() = default;
	XorBasis(std::initializer_list<UInt> values) { for (UInt x : values) insert(x); }
	explicit XorBasis(const std::vector<UInt> &values) { for (UInt x : values) insert(x); }
	int rank() const { return core.dimension; }
	bool empty() const { return rank() == 0; }
	count_type count() const { return count_type(1) << rank(); }
	void clear() { core = Core{}; }
	bool insert(UInt x) { return core.insert(x) >= 0; }
	UInt reduce(UInt x) const { return core.minimize(x); }
	bool contains(UInt x) const { return reduce(x) == 0; }
	UInt min_xor(UInt x = 0) const { return core.minimize(x); }
	UInt max_xor(UInt x = 0) const { return core.maximize(x); }
	count_type mex(UInt x = 0) const {
		if (!contains(x)) return 0;
		if (rank() == Bits) return count_type(1) << Bits;
		for (int i = 0; i < Bits; ++i) if (!core.at[i]) return count_type(1) << i;
		return count_type(1) << Bits;
	}
	std::optional<UInt> min_nonzero() const {
		if (empty()) return std::nullopt;
		return *std::min_element(core.row.begin(), core.row.begin() + rank());
	}
	std::span<const UInt> vectors_view() const & { return {core.row.data(), std::size_t(rank())}; }
	std::span<const UInt> vectors_view() const && = delete;
	std::vector<UInt> vectors() const {
		return {core.row.begin(), core.row.begin() + rank()};
	}
	XorBasis canonical() const {
		XorBasis result = *this;
		std::sort(result.core.row.begin(), result.core.row.begin() + rank());
		result.core.at.fill(0);
		for (int i = 0; i < rank(); ++i) {
			int p = Core::pivot(result.core.row[i]);
			result.core.at[p] = std::uint8_t(i + 1);
			for (int j = i + 1; j < rank(); ++j)
				if ((result.core.row[j] >> p) & 1) result.core.row[j] ^= result.core.row[i];
		}
		return result;
	}
	std::optional<UInt> coordinates(UInt x) const {
		UInt result = 0;
		for (int i = 0; i < rank(); ++i) if (UInt(x ^ core.row[i]) < x) {
			x ^= core.row[i]; result |= UInt(UInt(1) << i);
		}
		if (x) return std::nullopt;
		return result;
	}
	UInt combine(UInt coefficients) const {
		UInt result = 0;
		for (int i = 0; i < rank(); ++i) {
			if (coefficients & 1) result ^= core.row[i];
			coefficients >>= 1;
		}
		assert(!coefficients);
		return result;
	}
	std::optional<UInt> kth(count_type k, UInt x = 0) const {
		if (k >= count()) return std::nullopt;
		if (rank() == Bits) return UInt((x & UInt(~Core::mask)) | UInt(k));
		int remaining = rank();
		for (int i = Bits - 1; i >= 0; --i) if (core.at[i]) {
			--remaining;
			if (((x >> i) & 1) != ((k >> remaining) & 1)) x ^= core.row[core.at[i] - 1];
		}
		return x;
	}
	count_type count_less(count_type value, UInt x = 0) const {
		if (value >= (count_type(1) << Core::digits)) return count();
		UInt bound = UInt(value);
		UInt high = UInt(x & UInt(~Core::mask)), bound_high = UInt(bound & UInt(~Core::mask));
		if (high != bound_high) return high < bound_high ? count() : 0;
		if (rank() == Bits) return UInt(bound & Core::mask);
		count_type result = 0;
		int remaining = rank();
		for (int i = Bits - 1; i >= 0; --i) {
			bool target = (bound >> i) & 1;
			if (core.at[i]) {
				--remaining;
				if (target) result += count_type(1) << remaining;
				if (bool((x >> i) & 1) != target) x ^= core.row[core.at[i] - 1];
			} else if (bool((x >> i) & 1) != target) return result + (target ? count_type(1) << remaining : 0);
		}
		return result;
	}
	count_type count_leq(count_type value, UInt x = 0) const {
		if (value >= std::numeric_limits<UInt>::max()) return count();
		return count_less(value + 1, x);
	}
	count_type count_range(count_type lower, count_type upper, UInt x = 0) const {
		assert(lower <= upper);
		return count_less(upper, x) - count_less(lower, x);
	}
	std::optional<count_type> index_of(count_type value, UInt x = 0) const {
		if (value > std::numeric_limits<UInt>::max() || !contains(UInt(UInt(value) ^ x))) return std::nullopt;
		return count_less(value, x);
	}
	std::optional<UInt> lower_bound(count_type value, UInt x = 0) const { return kth(count_less(value, x), x); }
	std::optional<UInt> upper_bound(count_type value, UInt x = 0) const { return kth(count_leq(value, x), x); }
	std::optional<UInt> predecessor(count_type value, UInt x = 0) const {
		count_type k = count_less(value, x);
		return k ? kth(k - 1, x) : std::nullopt;
	}
	int merge(const XorBasis &other) {
		int before = rank();
		if (this != &other) for (int i = 0; i < other.rank(); ++i) {
			insert(other.core.row[i]);
			if (rank() == Bits) break;
		}
		return rank() - before;
	}
	bool is_subspace_of(const XorBasis &other) const {
		if (rank() > other.rank()) return false;
		for (int i = 0; i < rank(); ++i) if (!other.contains(core.row[i])) return false;
		return true;
	}
	bool operator==(const XorBasis &other) const { return rank() == other.rank() && is_subspace_of(other); }
	XorBasis intersection(const XorBasis &other) const {
		if (core.dimension == Bits || this == &other) return other;
		if (other.core.dimension == Bits) return *this;
		if (rank() < other.rank()) return other.intersection(*this);
		return intersection_range({other.core.row.data(), std::size_t(other.rank())});
	}
	template <class Range>
	requires requires(const Range &values) { std::span<const UInt>(values); }
	XorBasis intersection(const Range &values) const { return intersection_range(std::span<const UInt>(values)); }

	XorBasis orthogonal_complement() const {
		auto reduced = canonical();
		XorBasis result;
		for (int j = 0; j < Bits; ++j) if (!reduced.core.at[j]) {
			UInt x = UInt(UInt(1) << j);
			for (int i = 0; i < rank(); ++i) if ((reduced.core.row[i] >> j) & 1) x |= UInt(UInt(1) << Core::pivot(reduced.core.row[i]));
			result.insert(x);
		}
		return result;
	}
	XorBasis &operator|=(const XorBasis &other) { merge(other); return *this; }
	XorBasis &operator&=(const XorBasis &other) { return *this = intersection(other); }
	friend XorBasis operator|(XorBasis a, const XorBasis &b) { a.merge(b); return a; }
	friend XorBasis operator&(const XorBasis &a, const XorBasis &b) { return a.intersection(b); }
};

template <class UInt = std::uint64_t, int Bits = std::numeric_limits<UInt>::digits>
class RollbackXorBasis {
	XorBasis<UInt, Bits> current;
	std::vector<int> history;

  public:
	const XorBasis<UInt, Bits> &basis() const { return current; }
	std::size_t snapshot() const { return history.size(); }
	bool insert(UInt x) {
		history.push_back(-1);
		int i = current.core.insert(x);
		history.back() = i;
		return i >= 0;
	}
	void undo() {
		assert(!history.empty());
		int i = history.back(); history.pop_back();
		if (i >= 0) {
			current.core.at[current.core.pivot(current.core.row[i])] = 0;
			current.core.row[i] = 0; --current.core.dimension;
		}
	}
	void rollback(std::size_t token) { assert(token <= history.size()); while (history.size() > token) undo(); }
	void clear() { current.clear(); history.clear(); }
};

template <class UInt = std::uint64_t, int Bits = std::numeric_limits<UInt>::digits>
class PrefixXorBasis {
	using Core = xor_basis_detail::Core<UInt, Bits>;
	std::array<UInt, Bits> row{};
	std::array<std::size_t, Bits> position{};
	std::size_t length = 0;

  public:
	std::size_t size() const { return length; }
	void clear() { row.fill(0); position.fill(0); length = 0; }
	bool push_back(UInt x) {
		assert(Core::valid(x) && length < std::numeric_limits<std::size_t>::max());
		std::size_t p = ++length;
		while (x) {
			int i = Core::pivot(x);
			if (!row[i]) { row[i] = x; position[i] = p; return true; }
			if (position[i] < p) { std::swap(position[i], p); std::swap(row[i], x); }
			x ^= row[i];
		}
		return false;
	}
	XorBasis<UInt, Bits> basis(std::size_t lower = 0) const {
		assert(lower <= length);
		XorBasis<UInt, Bits> result;
		for (int i = Bits - 1; i >= 0; --i) if (position[i] > lower) {
			int k = result.core.dimension++;
			result.core.row[k] = row[i]; result.core.at[i] = std::uint8_t(k + 1);
		}
		return result;
	}
	int rank(std::size_t lower = 0) const {
		assert(lower <= length);
		int result = 0;
		for (std::size_t p : position) result += p > lower;
		return result;
	}
	UInt min_xor(std::size_t lower = 0, UInt x = 0) const {
		assert(lower <= length);
		for (int i = Bits - 1; i >= 0; --i) if (position[i] > lower) x = std::min(x, UInt(x ^ row[i]));
		return x;
	}
	UInt max_xor(std::size_t lower = 0, UInt x = 0) const {
		assert(lower <= length);
		for (int i = Bits - 1; i >= 0; --i) if (position[i] > lower) x = std::max(x, UInt(x ^ row[i]));
		return x;
	}
	bool contains(std::size_t lower, UInt x) const { return min_xor(lower, x) == 0; }
};

template <class UInt = std::uint64_t, int Bits = std::numeric_limits<UInt>::digits>
class XorBasisWithWitness {
	using Core = xor_basis_detail::Core<UInt, Bits>;
	XorBasis<UInt, Bits> current;
	std::array<UInt, Bits> source{};
	std::array<std::size_t, Bits> index{};
	std::size_t length = 0;

  public:
	const XorBasis<UInt, Bits> &basis() const { return current; }
	std::size_t size() const { return length; }
	void clear() { current.clear(); source.fill(0); length = 0; }
	bool insert(UInt x) {
		assert(Core::valid(x) && length < std::numeric_limits<std::size_t>::max());
		std::size_t id = length++;
		if (current.rank() == Bits) return false;
		UInt mask = UInt(UInt(1) << current.rank());
		for (int i = 0; i < current.rank(); ++i) if (UInt(x ^ current.core.row[i]) < x) {
			x ^= current.core.row[i]; mask ^= source[i];
		}
		if (!x) return false;
		int k = current.core.dimension++;
		index[k] = id; source[k] = mask; current.core.row[k] = x;
		current.core.at[Core::pivot(x)] = std::uint8_t(k + 1);
		return true;
	}
	std::optional<std::vector<std::size_t>> represent(UInt x) const {
		if (!Core::valid(x)) return std::nullopt;
		UInt mask = 0;
		for (int i = 0; i < current.rank(); ++i) if (UInt(x ^ current.core.row[i]) < x) {
			x ^= current.core.row[i]; mask ^= source[i];
		}
		if (x) return std::nullopt;
		std::vector<std::size_t> result;
		while (mask) {
			int i = std::countr_zero(std::uint64_t(mask));
			result.push_back(index[i]); mask &= UInt(mask - 1);
		}
		return result;
	}
};