#include <algorithm>
#include <bitset>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
 
static const std::pair<int, int> kBishopDirections[] = {
	{1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
 
static bool valid_square(int row, int col) {
	return row >= 0 && col >= 0 && row < 8 && col < 8;
}
 
template <typename TCont>
auto relevant_squares(int square, const TCont& directions) {
	std::vector<int> res;
	int start_row = square / 8;
	int start_col = square % 8;
	for (auto direction : directions) {
		auto dst_row = start_row + direction.first;
		auto dst_col = start_col + direction.second;
		// If the next square in this direction is invalid, the current square
		// is at the board's edge and should not be added.
		while (valid_square(dst_row + direction.first, dst_col + direction.second)) {
			res.push_back(dst_row * 8 + dst_col);
			dst_row += direction.first;
			dst_col += direction.second;
		}
	}
	std::sort(res.begin(), res.end());
	return res;
}
 
template <typename TCont, typename TOp>
void for_each_bitboard(const TCont& squares, TOp op) {
	const auto i_max = 1ull << squares.size();
	for (auto i = 0ull; i < i_max; ++i) {
		auto bitboard = 0ull;
		auto bits = i;
		for (const auto sq : squares) {
			if (bits & 1) {
				bitboard |= 1ull << sq;
			}
			bits >>= 1;
		}
		op(bitboard);
	}
}
 
template <typename TMagic, typename TBitboard>
auto index(TMagic magic, TBitboard bitboard) {
	const auto shift = magic >> 56;
	return (bitboard * magic) >> shift;
}
 
template <typename TBitboard>
void print_board(TBitboard bitboard) {
	auto reverse_8bits = [](auto b) {
		b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
		b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
		b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
		return b;
	};
 
	for (int shift = 56; shift >= 0; shift -= 8) {
		auto row = reverse_8bits((bitboard >> shift) & 0xFF);
		std::cout << std::bitset<8>(row);
		if (shift)
			std::cout << "\n";
	}
}
 
int main() {
	// const auto square = 2; // C1
	const auto square = 62; // G8
	const auto squares = relevant_squares(square, kBishopDirections);
	std::cout << "Relevant squares:";
	for (auto wtf : squares) {
		std::cout << " " << wtf;
	}
	std::cout << std::endl;
 
	std::vector<int> bits(64);
	std::iota(bits.begin(), bits.end(), 0);
	std::reverse(bits.begin(), bits.end());
	for (auto square : squares) {
		std::cout << "<<" << std::setw(2) << square << ": ";
		auto shifted = bits;
		shifted.erase(shifted.begin(), shifted.begin() + square);
		for (auto bit : shifted) {
			std::cout << std::setw(3) << bit;
		}
		std::cout << "\n";
	}
	std::cout << "\n";
 
	const auto magic = 0x3c007f2491c5c260;
	std::cout << "Magic:";
	for (int i = 56; i >= 0; i -= 8) {
		std::cout << std::setw(9) << std::bitset<8>(magic >> i);
		std::cout << "(" << i << ")";
	}
	std::cout << "\n";
	for (auto square : squares) {
		std::cout << "<<" << std::setw(2) << square << ": ";
		auto str = std::bitset<64>(magic << square).to_string();
		for (auto bit : str) {
			std::cout << std::setw(2) << bit;
		}
		std::cout << "\n";
	}
	std::cout << "\n";
 
	for_each_bitboard(squares, [&](auto bitboard) {
		print_board(bitboard);
		std::cout << " ==> ";
		std::cout << std::setw(3) << std::dec << index(magic, bitboard);
		std::cout << "\n\n";
	});
}

I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGJpdHNldD4KI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDx2ZWN0b3I+CgpzdGF0aWMgY29uc3Qgc3RkOjpwYWlyPGludCwgaW50PiBrQmlzaG9wRGlyZWN0aW9uc1tdID0gewoJezEsIDF9LCB7LTEsIDF9LCB7MSwgLTF9LCB7LTEsIC0xfX07CgpzdGF0aWMgYm9vbCB2YWxpZF9zcXVhcmUoaW50IHJvdywgaW50IGNvbCkgewoJcmV0dXJuIHJvdyA+PSAwICYmIGNvbCA+PSAwICYmIHJvdyA8IDggJiYgY29sIDwgODsKfQoKdGVtcGxhdGUgPHR5cGVuYW1lIFRDb250PgphdXRvIHJlbGV2YW50X3NxdWFyZXMoaW50IHNxdWFyZSwgY29uc3QgVENvbnQmIGRpcmVjdGlvbnMpIHsKCXN0ZDo6dmVjdG9yPGludD4gcmVzOwoJaW50IHN0YXJ0X3JvdyA9IHNxdWFyZSAvIDg7CglpbnQgc3RhcnRfY29sID0gc3F1YXJlICUgODsKCWZvciAoYXV0byBkaXJlY3Rpb24gOiBkaXJlY3Rpb25zKSB7CgkJYXV0byBkc3Rfcm93ID0gc3RhcnRfcm93ICsgZGlyZWN0aW9uLmZpcnN0OwoJCWF1dG8gZHN0X2NvbCA9IHN0YXJ0X2NvbCArIGRpcmVjdGlvbi5zZWNvbmQ7CgkJLy8gSWYgdGhlIG5leHQgc3F1YXJlIGluIHRoaXMgZGlyZWN0aW9uIGlzIGludmFsaWQsIHRoZSBjdXJyZW50IHNxdWFyZQoJCS8vIGlzIGF0IHRoZSBib2FyZCdzIGVkZ2UgYW5kIHNob3VsZCBub3QgYmUgYWRkZWQuCgkJd2hpbGUgKHZhbGlkX3NxdWFyZShkc3Rfcm93ICsgZGlyZWN0aW9uLmZpcnN0LCBkc3RfY29sICsgZGlyZWN0aW9uLnNlY29uZCkpIHsKCQkJcmVzLnB1c2hfYmFjayhkc3Rfcm93ICogOCArIGRzdF9jb2wpOwoJCQlkc3Rfcm93ICs9IGRpcmVjdGlvbi5maXJzdDsKCQkJZHN0X2NvbCArPSBkaXJlY3Rpb24uc2Vjb25kOwoJCX0KCX0KCXN0ZDo6c29ydChyZXMuYmVnaW4oKSwgcmVzLmVuZCgpKTsKCXJldHVybiByZXM7Cn0KCnRlbXBsYXRlIDx0eXBlbmFtZSBUQ29udCwgdHlwZW5hbWUgVE9wPgp2b2lkIGZvcl9lYWNoX2JpdGJvYXJkKGNvbnN0IFRDb250JiBzcXVhcmVzLCBUT3Agb3ApIHsKCWNvbnN0IGF1dG8gaV9tYXggPSAxdWxsIDw8IHNxdWFyZXMuc2l6ZSgpOwoJZm9yIChhdXRvIGkgPSAwdWxsOyBpIDwgaV9tYXg7ICsraSkgewoJCWF1dG8gYml0Ym9hcmQgPSAwdWxsOwoJCWF1dG8gYml0cyA9IGk7CgkJZm9yIChjb25zdCBhdXRvIHNxIDogc3F1YXJlcykgewoJCQlpZiAoYml0cyAmIDEpIHsKCQkJCWJpdGJvYXJkIHw9IDF1bGwgPDwgc3E7CgkJCX0KCQkJYml0cyA+Pj0gMTsKCQl9CgkJb3AoYml0Ym9hcmQpOwoJfQp9Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVE1hZ2ljLCB0eXBlbmFtZSBUQml0Ym9hcmQ+CmF1dG8gaW5kZXgoVE1hZ2ljIG1hZ2ljLCBUQml0Ym9hcmQgYml0Ym9hcmQpIHsKCWNvbnN0IGF1dG8gc2hpZnQgPSBtYWdpYyA+PiA1NjsKCXJldHVybiAoYml0Ym9hcmQgKiBtYWdpYykgPj4gc2hpZnQ7Cn0KCnRlbXBsYXRlIDx0eXBlbmFtZSBUQml0Ym9hcmQ+CnZvaWQgcHJpbnRfYm9hcmQoVEJpdGJvYXJkIGJpdGJvYXJkKSB7CglhdXRvIHJldmVyc2VfOGJpdHMgPSBbXShhdXRvIGIpIHsKCQliID0gKGIgJiAweEYwKSA+PiA0IHwgKGIgJiAweDBGKSA8PCA0OwoJCWIgPSAoYiAmIDB4Q0MpID4+IDIgfCAoYiAmIDB4MzMpIDw8IDI7CgkJYiA9IChiICYgMHhBQSkgPj4gMSB8IChiICYgMHg1NSkgPDwgMTsKCQlyZXR1cm4gYjsKCX07CgoJZm9yIChpbnQgc2hpZnQgPSA1Njsgc2hpZnQgPj0gMDsgc2hpZnQgLT0gOCkgewoJCWF1dG8gcm93ID0gcmV2ZXJzZV84Yml0cygoYml0Ym9hcmQgPj4gc2hpZnQpICYgMHhGRik7CgkJc3RkOjpjb3V0IDw8IHN0ZDo6Yml0c2V0PDg+KHJvdyk7CgkJaWYgKHNoaWZ0KQoJCQlzdGQ6OmNvdXQgPDwgIlxuIjsKCX0KfQoKaW50IG1haW4oKSB7CgkvLyBjb25zdCBhdXRvIHNxdWFyZSA9IDI7IC8vIEMxCgljb25zdCBhdXRvIHNxdWFyZSA9IDYyOyAvLyBHOAoJY29uc3QgYXV0byBzcXVhcmVzID0gcmVsZXZhbnRfc3F1YXJlcyhzcXVhcmUsIGtCaXNob3BEaXJlY3Rpb25zKTsKCXN0ZDo6Y291dCA8PCAiUmVsZXZhbnQgc3F1YXJlczoiOwoJZm9yIChhdXRvIHd0ZiA6IHNxdWFyZXMpIHsKCQlzdGQ6OmNvdXQgPDwgIiAiIDw8IHd0ZjsKCX0KCXN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7CgoJc3RkOjp2ZWN0b3I8aW50PiBiaXRzKDY0KTsKCXN0ZDo6aW90YShiaXRzLmJlZ2luKCksIGJpdHMuZW5kKCksIDApOwoJc3RkOjpyZXZlcnNlKGJpdHMuYmVnaW4oKSwgYml0cy5lbmQoKSk7Cglmb3IgKGF1dG8gc3F1YXJlIDogc3F1YXJlcykgewoJCXN0ZDo6Y291dCA8PCAiPDwiIDw8IHN0ZDo6c2V0dygyKSA8PCBzcXVhcmUgPDwgIjogIjsKCQlhdXRvIHNoaWZ0ZWQgPSBiaXRzOwoJCXNoaWZ0ZWQuZXJhc2Uoc2hpZnRlZC5iZWdpbigpLCBzaGlmdGVkLmJlZ2luKCkgKyBzcXVhcmUpOwoJCWZvciAoYXV0byBiaXQgOiBzaGlmdGVkKSB7CgkJCXN0ZDo6Y291dCA8PCBzdGQ6OnNldHcoMykgPDwgYml0OwoJCX0KCQlzdGQ6OmNvdXQgPDwgIlxuIjsKCX0KCXN0ZDo6Y291dCA8PCAiXG4iOwoKCWNvbnN0IGF1dG8gbWFnaWMgPSAweDNjMDA3ZjI0OTFjNWMyNjA7CglzdGQ6OmNvdXQgPDwgIk1hZ2ljOiI7Cglmb3IgKGludCBpID0gNTY7IGkgPj0gMDsgaSAtPSA4KSB7CgkJc3RkOjpjb3V0IDw8IHN0ZDo6c2V0dyg5KSA8PCBzdGQ6OmJpdHNldDw4PihtYWdpYyA+PiBpKTsKCQlzdGQ6OmNvdXQgPDwgIigiIDw8IGkgPDwgIikiOwoJfQoJc3RkOjpjb3V0IDw8ICJcbiI7Cglmb3IgKGF1dG8gc3F1YXJlIDogc3F1YXJlcykgewoJCXN0ZDo6Y291dCA8PCAiPDwiIDw8IHN0ZDo6c2V0dygyKSA8PCBzcXVhcmUgPDwgIjogIjsKCQlhdXRvIHN0ciA9IHN0ZDo6Yml0c2V0PDY0PihtYWdpYyA8PCBzcXVhcmUpLnRvX3N0cmluZygpOwoJCWZvciAoYXV0byBiaXQgOiBzdHIpIHsKCQkJc3RkOjpjb3V0IDw8IHN0ZDo6c2V0dygyKSA8PCBiaXQ7CgkJfQoJCXN0ZDo6Y291dCA8PCAiXG4iOwoJfQoJc3RkOjpjb3V0IDw8ICJcbiI7CgoJZm9yX2VhY2hfYml0Ym9hcmQoc3F1YXJlcywgWyZdKGF1dG8gYml0Ym9hcmQpIHsKCQlwcmludF9ib2FyZChiaXRib2FyZCk7CgkJc3RkOjpjb3V0IDw8ICIgPT0+ICI7CgkJc3RkOjpjb3V0IDw8IHN0ZDo6c2V0dygzKSA8PCBzdGQ6OmRlYyA8PCBpbmRleChtYWdpYywgYml0Ym9hcmQpOwoJCXN0ZDo6Y291dCA8PCAiXG5cbiI7Cgl9KTsKfQ==