#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

// Implements a linear independence–based solvability check for linear equations over the field F2
// using XOR Gaussian elimination in compressed form.
// The method is widely used in competitive programming for problems involving XOR combinations.
static bool check_solvability_over_gf2(
	const std::vector<uint16_t>& masks, uint16_t target)
{
	static std::vector<uint16_t> basis;
	basis.clear();
	for (uint16_t m : masks)
	{
		for (uint16_t b : basis)
			m = std::min(m, (uint16_t)(m ^ b));
		if (m > 0)
		{
			basis.push_back(m);
			std::sort(basis.rbegin(), basis.rend());
		}
	}
	for (uint16_t b : basis)
		target = std::min(target, (uint16_t)(target ^ b));
	return target == 0;
}

// Mod 2 matrix packed into 16 bit integer
struct mat {
	uint16_t pack = 0;  // 16 bits to store 4x4 matrix

	// Default constructor
	mat() = default;

	// Constructor from uint16_t
	explicit mat(uint16_t value) : pack(value) {}

	// Compute bit index from row (i) and column (j)
	constexpr int index(int i, int j) const { return i * 4 + j; }

	// Get the bit at (i,j)
	bool get(int i, int j) const {
		return (pack >> index(i, j)) & 1;
	}

	// Set the bit at (i,j) to 1
	void set(int i, int j) {
		pack |= (1 << index(i, j));
	}

	// Clear the bit at (i,j) to 0
	void clear(int i, int j) {
		pack &= ~(1 << index(i, j));
	}

	// Toggle the bit at (i,j)
	void toggle(int i, int j) {
		pack ^= (1 << index(i, j));
	}

	// Print as 4x4 matrix
	void print() const {
		for (int i = 0; i < 4; ++i) {
			for (int j = 0; j < 4; ++j) {
				if (j != 0)std::cout << ", ";
				std::cout << get(i, j);
			}
			std::cout << "\n";
		}
	}

	mat add(const mat& m) const {
		return mat(pack ^ m.pack);
	}

	// Comparison operators
	bool operator==(const mat& other) const { return pack == other.pack; }
	bool operator!=(const mat& other) const { return pack != other.pack; }
	bool operator<(const mat& other) const { return pack < other.pack; }
	bool operator<=(const mat& other) const { return pack <= other.pack; }
	bool operator>(const mat& other) const { return pack > other.pack; }
	bool operator>=(const mat& other) const { return pack >= other.pack; }
};

// Uses check_solvability_over_gf2 to check if all matrices in 'want'
// are representable as some linear combination of masks
vector<mat> want;
bool is_valid_basis(const std::vector<mat>& masks)
{
	static vector<uint16_t> flat;
	flat.clear();
	for (const auto& m : masks) {
		flat.push_back(m.pack);
	}

	for (const auto& m : want) {
		if (!check_solvability_over_gf2(flat, m.pack))
			return false;
	}
	return true;
}

int main(int argc, char* argv[])
{
	{
		mat m;
		m.set(0, 0);
		m.set(1, 2);
		want.push_back(m);
	}
	{
		mat m;
		m.set(0, 1);
		m.set(1, 3);
		want.push_back(m);
	}
	{
		mat m;
		m.set(2, 0);
		m.set(3, 2);
		want.push_back(m);
	}
	{
		mat m;
		m.set(2, 1);
		m.set(3, 3);
		want.push_back(m);
	}

	vector<mat> mats;
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			for (int k = 0; k < 4; ++k) {
				for (int l = 0; l < 4; ++l) {
					mat cur;
					cur.set(i, j);
					cur.set(k, j);
					cur.set(i, l);
					cur.set(k, l);
					mats.push_back(cur);
				}
			}
		}
	}

	sort(mats.begin(), mats.end());
	const auto it = unique(mats.begin(), mats.end());
	mats.erase(it, mats.end());

	long long evals = 0;
	vector<mat> basis;
	for (int i1 = 0; i1 < mats.size(); ++i1) {
		for (int i2 = i1 + 1; i2 < mats.size(); ++i2) {
			for (int i3 = i2 + 1; i3 < mats.size(); ++i3) {
				for (int i4 = i3 + 1; i4 < mats.size(); ++i4) {
					for (int i5 = i4 + 1; i5 < mats.size(); ++i5) {
						for (int i6 = i5 + 1; i6 < mats.size(); ++i6) {
							for (int i7 = i6 + 1; i7 < mats.size(); ++i7) {
								evals++;
								if (evals % 1000000000 == 0) {
									printf("%lld\n", evals);
								}

								basis = { mats[i1],mats[i2],mats[i3],mats[i4],mats[i5],mats[i6],mats[i7] };

								if (is_valid_basis(basis)) {
									printf("start");
									for (const auto& b : basis) {
										b.print();
									}
									printf("end");
								}
							}
						}
					}
				}
			}
		}
	}

	return 0;
}