#include <iostream>
#include <cstdint>
#include <vector>
#include <queue>
#include <type_traits>
#include <random>
#include <array>
#include <utility>
#include <string>
#include <queue>
#include <intrin.h>
#include <unordered_map>
#include <chrono>
#include <unordered_set>
#include <memory>
#include <stdio.h>
#include <functional>
#include <memory>

template <size_t ChunkSize>
class TFixedAllocator {
    union TNode { // union
        char data[ChunkSize];
        TNode* next; // free chunks of memory form a stack; pointer to the next (or nullptr)
    };

    TNode* free; // the topmost free chunk of memory (or nullptr)
    std::vector<TNode*> pools; // all allocated pools of memory
    int size = 1; // size of the last allocated pool of memory
    const int MAX_SIZE = 1024;

    void new_pool() { // allocate new pool of memory
        if (size < MAX_SIZE) {
            size *= 2;
        }
        free = new TNode[size];

        // form a stack of chunks of this pool
        pools.push_back(free);
        for (int i = 0; i < size; ++i) {
            free[i].next = &free[i + 1];
        }
        free[size - 1].next = nullptr;
    }
    TFixedAllocator() { // private for singleton
        new_pool();
    }
public:
    TFixedAllocator(const TFixedAllocator&) = delete; // for singleton
    static TFixedAllocator& instance() { // singleton
        static TFixedAllocator instance;
        return instance;
    }
    void* allocate() {
        if (!free) {
            new_pool();
        }
        TNode* result = free; // allocate the topmost element (saved in free)
        free = free->next; // and pop it from the stack of free chunks
        return static_cast<void*>(result);
    }
    void deallocate(void* elem) {
        TNode* node = static_cast<TNode*>(elem);

        // add to the stack of chunks
        node->next = free;
        free = node;
    }
    ~TFixedAllocator() {
        for (auto ptr : pools) {
            delete ptr;
        }
    }
};
template <class T>
class TFSBAllocator : std::allocator<T> {
public:
    using value_type = T;
    using pointer = T *;
    using const_pointer = const T*;
    using reference = T &;
    using const_reference = const T &;

    template <class U>
    class rebind {
    public:
        using other = TFSBAllocator<U>;
    };

    constexpr TFSBAllocator() noexcept { // construct default allocator (do nothing)
    }
    constexpr TFSBAllocator(const TFSBAllocator&) noexcept = default;
    template <class _Other>
    constexpr TFSBAllocator(const TFSBAllocator<_Other>&) noexcept { // construct from a related allocator (do nothing)
    }

    pointer allocate(size_t n) {
        if (n == 1) {
            return static_cast<T*>(TFixedAllocator<sizeof(T)>::instance().allocate());
        }
        else {
            return std::allocator<T>().allocate(n);
        }
    }
    void deallocate(pointer p, size_t n) {
        if (n == 1) {
            TFixedAllocator<sizeof(T)>::instance().deallocate(static_cast<void*>(p));
        }
        else {
            return std::allocator<T>().deallocate(p, n);
        }
    }
    void construct(pointer p, const_reference t) {
        new (p) T(t);
    }
    void destroy(pointer p) {
        p->~T();
    }
};

template <typename T, typename V>
using MapType = std::unordered_map<T, V, std::hash<T>, std::equal_to<T>, TFSBAllocator< std::pair<const T, V>>>;

static constexpr int width = 6;
static constexpr int height = 6;

static constexpr int reportEveryNPositions = 1<<16;

std::uint64_t murmur64(std::uint64_t h) {
    h ^= h >> 33;
    h *= 0xff51afd7ed558ccdULL;
    h ^= h >> 33;
    h *= 0xc4ceb9fe1a85ec53ULL;
    h ^= h >> 33;
    return h;
}

enum struct PieceType : std::uint8_t
{
    None = 0,
    King, // 1+
    Knight, // ~1/2
    Dabbaba, // ~2+
    NumPieceTypes
};

enum struct Color : std::uint8_t
{
    White = 0,
    Black = 1,
    NumColors
};

Color oppositeColor(Color color)
{
    return color == Color::White ? Color::Black : Color::White;
}

template <typename EnumT>
constexpr auto ordinal(EnumT e)
{
    return static_cast<std::underlying_type_t<EnumT>>(e);
}

template <typename EnumT, typename IntT>
constexpr EnumT fromOrdinal(IntT v)
{
    return static_cast<EnumT>(v);
}

constexpr int numPieceTypes = ordinal(PieceType::NumPieceTypes);
constexpr int numColors = ordinal(Color::NumColors);

struct Piece
{
    static_assert(numColors == 2, "");

    static constexpr Piece none()
    {
        return Piece(PieceType::None, Color::White);
    }

    constexpr Piece() :
        Piece(PieceType::None, Color::White)
    {

    }

    constexpr Piece(PieceType type, Color color) :
        m_index((ordinal(type) << 1) | ordinal(color))
    {
    }

    constexpr Piece& operator=(const Piece& other) = default;

    constexpr friend bool operator==(Piece lhs, Piece rhs)
    {
        return lhs.m_index == rhs.m_index;
    }

    constexpr friend bool operator!=(Piece lhs, Piece rhs)
    {
        return !(lhs == rhs);
    }

    constexpr PieceType type() const
    {
        return fromOrdinal<PieceType>(m_index >> 1);
    }

    constexpr Color color() const
    {
        return fromOrdinal<Color>(m_index & 1);
    }

    std::uint64_t hash() const
    {
        return std::hash<std::uint8_t>{}(m_index);
    }

    constexpr std::uint8_t index() const
    {
        return m_index;
    }

private:
    std::uint8_t m_index; // lowest bit is a color, 7 highest bits are a piece type
};

constexpr int numAllPieces = numPieceTypes * numColors;

template <>
constexpr auto ordinal(Piece e)
{
    return e.index();
}

struct Square
{
    static constexpr Square fromIndex(int idx)
    {
        return Square(idx);
    }

    static constexpr Square none()
    {
        return Square{};
    }

    constexpr Square() :
        m_index(width*height)
    {

    }

    constexpr Square(int x, int y) :
        m_index(x * height + y)
    {

    }

    constexpr friend bool operator==(Square lhs, Square rhs)
    {
        return lhs.m_index == rhs.m_index;
    }

    constexpr friend bool operator!=(Square lhs, Square rhs)
    {
        return !(lhs == rhs);
    }

    constexpr std::uint8_t index() const
    {
        return m_index;
    }

    constexpr int x() const
    {
        return m_index / height;
    }

    constexpr int y() const
    {
        return m_index % height;
    }

private:
    std::uint8_t m_index;

    constexpr Square(int idx) :
        m_index(idx)
    {
    }
};

struct Move
{
    static Move none()
    {
        return Move(-1, Square(0, 0));
    }

    Move(std::int8_t fromIdx, Square to) :
        m_fromIdx(fromIdx),
        m_to(to)
    {
    }

    friend bool operator==(Move lhs, Move rhs)
    {
        return lhs.m_fromIdx == rhs.m_fromIdx && lhs.m_to == rhs.m_to;
    }

    std::int8_t fromIdx() const
    {
        return m_fromIdx;
    }

    Square to() const
    {
        return m_to;
    }

    bool isNone() const
    {
        return m_fromIdx == -1;
    }

private:
    std::int8_t m_fromIdx;
    Square m_to;
};

struct Offset
{
    constexpr Offset(int x, int y) :
        m_dx(x),
        m_dy(y)
    {
    }

    constexpr std::int8_t dx() const
    {
        return m_dx;
    }

    constexpr std::int8_t dy() const
    {
        return m_dy;
    }

private:
    std::int8_t m_dx;
    std::int8_t m_dy;
};

struct BitBoardLayer
{
    // bits counted from the LSB

    static constexpr BitBoardLayer none()
    {
        return BitBoardLayer{};
    }

    static constexpr BitBoardLayer all()
    {
        return ~none();
    }

    constexpr BitBoardLayer() :
        m_squares(0)
    {
    }

    constexpr bool isEmpty() const
    {
        return m_squares == 0;
    }

    constexpr bool isSet(Square sq) const
    {
        return !!((m_squares >> sq.index()) & 1ull);
    }

    constexpr void set(Square sq)
    {
        m_squares |= (1ull << sq.index());
    }

    constexpr void unset(Square sq)
    {
        m_squares &= ~(1ull << sq.index());
    }

    constexpr BitBoardLayer operator~() const
    {
        BitBoardLayer bb = *this;
        bb.m_squares = ~m_squares;
        return bb;
    }

    constexpr BitBoardLayer& operator^=(Square sq)
    {
        m_squares ^= (1ull << sq.index());
        return *this;
    }

    constexpr BitBoardLayer& operator&=(Square sq)
    {
        m_squares &= (1ull << sq.index());
        return *this;
    }

    constexpr BitBoardLayer& operator|=(Square sq)
    {
        m_squares |= (1ull << sq.index());
        return *this;
    }

    constexpr BitBoardLayer operator^(Square sq) const
    {
        BitBoardLayer bb = *this;
        bb ^= sq;
        return bb;
    }

    constexpr BitBoardLayer operator&(Square sq) const
    {
        BitBoardLayer bb = *this;
        bb &= sq;
        return bb;
    }

    constexpr BitBoardLayer operator|(Square sq) const
    {
        BitBoardLayer bb = *this;
        bb |= sq;
        return bb;
    }

    constexpr BitBoardLayer& operator^=(BitBoardLayer rhs)
    {
        m_squares ^= rhs.m_squares;
        return *this;
    }

    constexpr BitBoardLayer& operator&=(BitBoardLayer rhs)
    {
        m_squares &= rhs.m_squares;
        return *this;
    }

    constexpr BitBoardLayer& operator|=(BitBoardLayer rhs)
    {
        m_squares |= rhs.m_squares;
        return *this;
    }

    constexpr BitBoardLayer operator^(BitBoardLayer sq) const
    {
        BitBoardLayer bb = *this;
        bb ^= sq;
        return bb;
    }

    constexpr BitBoardLayer operator&(BitBoardLayer sq) const
    {
        BitBoardLayer bb = *this;
        bb &= sq;
        return bb;
    }

    constexpr BitBoardLayer operator|(BitBoardLayer sq) const
    {
        BitBoardLayer bb = *this;
        bb |= sq;
        return bb;
    }

    int count() const
    {
        return __popcnt64(m_squares);
    }

    bool any() const
    {
        return !!m_squares;
    }

    Square firstSquare() const
    {
        unsigned long idx;
        _BitScanReverse64(&idx, m_squares);
        return Square::fromIndex(idx);
    }

    constexpr BitBoardLayer& operator=(const BitBoardLayer& other) = default;

private:
    std::uint64_t m_squares;
};

void print(BitBoardLayer bb)
{
    std::string s;

    for (int y = 0; y < height; ++y)
    {
        for (int x = 0; x < width; ++x)
        {
            if (bb.isSet(Square(x, y)))
            {
                s += '1';
            }
            else
            {
                s += '0';
            }
        }

        s += '\n';
    }

    std::cout << s;
}

struct Board
{
    static constexpr int numDabbabas = 4;
    static constexpr int numPieces = 2 + 1 + numDabbabas;
    static constexpr Piece availablePieces[] = {
        Piece(PieceType::King, Color::White),
        Piece(PieceType::King, Color::Black),
        Piece(PieceType::Knight, Color::Black),
        Piece(PieceType::Dabbaba, Color::White),
        Piece(PieceType::Dabbaba, Color::White),
        Piece(PieceType::Dabbaba, Color::White),
        Piece(PieceType::Dabbaba, Color::White)
    };

    static constexpr int whites[] = { 0, 3, 4, 5, 6 };
    static constexpr int blacks[] = { 1, 2 };

    Board()
    {
        std::fill(std::begin(m_pieces), std::end(m_pieces), Square::none());
    }

    friend bool operator==(const Board& lhs, const Board& rhs)
    {
        return std::equal(std::begin(lhs.m_pieces), std::end(lhs.m_pieces), std::begin(rhs.m_pieces));
    }

    Piece at(Square sq) const
    {
        for (int i = 0; i < numPieces; ++i)
        {
            if (m_pieces[i] == sq)
            {
                return availablePieces[i];
            }
        }

        return Piece::none();
    }

    void order()
    {
        auto end = std::end(m_pieces);
        std::sort(end - numDabbabas, end, [](Square lhs, Square rhs) {return lhs.index() < rhs.index(); });
    }

    void doMove(const Move& move)
    {
        const Square from = m_pieces[move.fromIdx()];
        const Square to = move.to();

        for (int i = 0; i < numPieces; ++i)
        {
            if (m_pieces[i] == to)
            {
                m_pieces[i] = Square::none();
            }
        }
        m_pieces[move.fromIdx()] = to;

        order();
    }

    void place(const Piece& piece, Square sq)
    {
        for (int i = 0; i < numPieces; ++i)
        {
            if (m_pieces[i] == sq)
            {
                m_pieces[i] = Square::none();
            }
        }

        int idx = -1;
        if (piece == Piece(PieceType::King, Color::White))
        {
            idx = 0;
        }
        else if (piece == Piece(PieceType::King, Color::Black))
        {
            idx = 1;
        }
        else if (piece.type() == PieceType::Knight)
        {
            idx = 2;
        }
        else
        {
            idx = 3;
            for (int i = 0; i < numDabbabas; ++i)
            {
                if (m_pieces[i + 3] == Square::none())
                {
                    idx = i + 3;
                }
            }
        }
        m_pieces[idx] = sq;

        order();
    }

    BitBoardLayer bbByColor(Color c) const
    {
        BitBoardLayer bb{};

        if (c == Color::White)
        {
            for (int i : whites)
            {
                const Square sq = m_pieces[i];
                if (sq != Square::none())
                {
                    bb |= sq;
                }
            }
        }
        else
        {
            for (int i : blacks)
            {
                const Square sq = m_pieces[i];
                if (sq != Square::none())
                {
                    bb |= sq;
                }
            }
        }

        return bb;
    }

    BitBoardLayer bb() const
    {
        BitBoardLayer bb{};

        for (int i = 0; i < numPieces; ++i)
        {
            const Square sq = m_pieces[i];
            if (sq != Square::none())
            {
                bb |= sq;
            }
        }

        return bb;
    }

    bool hasBothKings() const
    {
        return whiteKing() != Square::none() && blackKing() != Square::none();
    }

    BitBoardLayer bbAttackedByPiece(int i) const;

    BitBoardLayer bbAttackedByColor(Color color) const
    {
        BitBoardLayer bb{};

        if (color == Color::White)
        {
            for (int i : whites)
            {
                bb |= bbAttackedByPiece(i);
            }
        }
        else
        {
            for (int i : blacks)
            {
                bb |= bbAttackedByPiece(i);
            }
        }

        return bb;
    }

    bool hasNoKings() const
    {
        return whiteKing() == Square::none() && blackKing() == Square::none();
    }

    bool kingsAttackEachOther() const;

    Square whiteKing() const
    {
        return m_pieces[0];
    }

    Square blackKing() const
    {
        return m_pieces[1];
    }

    Square blackKnight() const
    {
        return m_pieces[2];
    }

    Square whiteDabbaba(int i) const
    {
        return m_pieces[3 + i];
    }

    Square pieceSquare(int i) const
    {
        return m_pieces[i];
    }

    const auto& pieces() const
    {
        return m_pieces;
    }

private:
    std::array<Square, numPieces> m_pieces;
};

template <PieceType PieceTypeV>
struct MoveGenerator;

template <int SizeV>
constexpr BitBoardLayer generateMovesForLeaper(Square sq, const std::array<Offset, SizeV>& offsets)
{
    BitBoardLayer bb{};

    const int x = sq.x();
    const int y = sq.y();

    for (auto&& offset : offsets)
    {
        const int xx = x + offset.dx();
        const int yy = y + offset.dy();
        if (xx < 0 || xx >= width || yy < 0 || yy >= height)
        {
            continue;
        }

        Square sq2(xx, yy);
        bb.set(sq2);
    }

    return bb;
}

template <int SizeV>
constexpr std::array<BitBoardLayer, width* height> generateMovesForLeaper(const std::array<Offset, SizeV>& offsets)
{
    std::array<BitBoardLayer, width* height> moves;

    for (int x = 0; x < width; ++x)
    {
        for (int y = 0; y < height; ++y)
        {
            const Square sq(x, y);

            moves[sq.index()] = generateMovesForLeaper(sq, offsets);
        }
    }

    return moves;
}

template <>
struct MoveGenerator<PieceType::Knight>
{
    BitBoardLayer movesFromSquare(const Board& position, Square from) const
    {
        const Color fromColor = position.at(from).color();
        return m_moves[from.index()] & ~(position.bbByColor(fromColor));
    }

    BitBoardLayer movesToSquare(const Board& position, Square to) const
    {
        return m_moves[to.index()] & ~(position.bb());
    }

    BitBoardLayer attacksFromSquare(const Board& position, Square from) const
    {
        return m_moves[from.index()];
    }

private:
    static constexpr std::array<Offset, 8> m_offsets{ { {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {-2, -1}, {-2, 1}, {2, -1}, {2, 1} } };
    static constexpr std::array<BitBoardLayer, width* height> m_moves = generateMovesForLeaper(m_offsets);
};

template <>
struct MoveGenerator<PieceType::Dabbaba>
{
    BitBoardLayer movesFromSquare(const Board& position, Square from) const
    {
        const Color fromColor = position.at(from).color();
        return m_moves[from.index()] & ~(position.bbByColor(fromColor));
    }

    BitBoardLayer movesToSquare(const Board& position, Square to) const
    {
        return m_moves[to.index()] & ~(position.bb());
    }

    BitBoardLayer attacksFromSquare(const Board& position, Square from) const
    {
        return m_moves[from.index()];
    }

private:
    static constexpr std::array<Offset, 4> m_offsets{ { {-2, 0}, {2, 0}, {0, -2}, {0, 2} } };
    static constexpr std::array<BitBoardLayer, width* height> m_moves = generateMovesForLeaper(m_offsets);
};

template <>
struct MoveGenerator<PieceType::King>
{
    BitBoardLayer movesFromSquare(const Board& position, Square from) const
    {
        const Color fromColor = position.at(from).color();
        return m_moves[from.index()] & ~(position.bbByColor(fromColor));
    }

    BitBoardLayer movesToSquare(const Board& position, Square to) const
    {
        return m_moves[to.index()] & ~(position.bb());
    }

    BitBoardLayer attacksFromSquare(const Board& position, Square from) const
    {
        return m_moves[from.index()];
    }

private:
    static constexpr std::array<Offset, 8> m_offsets{ { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1} } };
    static constexpr std::array<BitBoardLayer, width* height> m_moves = generateMovesForLeaper(m_offsets);
};

BitBoardLayer Board::bbAttackedByPiece(int i) const
{
    MoveGenerator<PieceType::Knight> knightMoveGenerator;
    MoveGenerator<PieceType::Dabbaba> dabbabaMoveGenerator;
    MoveGenerator<PieceType::King> kingMoveGenerator;

    const Square sq = m_pieces[i];
    if (sq == Square::none()) return {};
    PieceType pieceType = Board::availablePieces[i].type();

    BitBoardLayer bb{};

    switch (pieceType)
    {
    case PieceType::King:
        bb |= kingMoveGenerator.movesFromSquare(*this, sq);
        break;

    case PieceType::Knight:
        bb |= knightMoveGenerator.movesFromSquare(*this, sq);
        break;

    case PieceType::Dabbaba:
        bb |= dabbabaMoveGenerator.movesFromSquare(*this, sq);
        break;
    }

    return bb;
}

bool Board::kingsAttackEachOther() const
{
    MoveGenerator<PieceType::King> kingMoveGenerator;

    Square wk = whiteKing();
    Square bk = blackKing();

    return (kingMoveGenerator.attacksFromSquare(*this, wk) & bk).any();
}

struct Zobrist
{
    Zobrist()
    {
        std::mt19937_64 rng;
        std::uniform_int_distribution<std::uint64_t> d;
        std::generate_n(data(), width * height * numPieceTypes * numColors, [&]() {return d(rng); });

        for (int i = 0; i < width * height; ++i)
        {
            m_hash[i][Piece(PieceType::None, Color::White).index()] = m_hash[i][Piece(PieceType::None, Color::Black).index()];
        }

        m_sideChangeHash = d(rng);
    }

    std::uint64_t hash(const Board& board, Color sideToMove) const
    {
        std::uint64_t h = 0;

        for (int x = 0; x < width; ++x)
        {
            for (int y = 0; y < height; ++y)
            {
                const Square sq(x, y);

                h ^= m_hash[sq.index()][board.at(sq).index()];
            }
        }

        if (sideToMove == Color::Black)
        {
            h ^= m_sideChangeHash;
        }

        return h;
    }

    std::uint64_t emptySquareHash(Square sq) const
    {
        return m_hash[sq.index()][Piece::none().index()];
    }

    std::uint64_t hashAfterMove(std::uint64_t hash, const Board& board, const Move& move) const
    {
        const Square from = board.pieceSquare(move.fromIdx());
        const Square to = move.to();

        hash ^= m_hash[from.index()][board.at(from).index()];
        hash ^= emptySquareHash(from);

        hash ^= m_hash[to.index()][board.at(to).index()];
        hash ^= m_hash[to.index()][board.at(from).index()];

        hash ^= m_sideChangeHash;

        return hash;
    }

    std::uint64_t hashAfterPieceReplaced(std::uint64_t hash, const Board& board, const Piece& piece, Square sq) const
    {
        hash ^= m_hash[sq.index()][board.at(sq).index()];
        hash ^= m_hash[sq.index()][piece.index()];

        return hash;
    }

private:
    std::uint64_t m_hash[width * height][numAllPieces];
    std::uint64_t m_sideChangeHash;

    std::uint64_t* data()
    {
        return &(m_hash[0][0]);
    }
} g_zobrist{};

enum struct GameState
{
    Invalid,
    Win,
    Loss,
    Valid
};

struct Position;


struct Moves
{
    Moves() :
        m_moves{}
    {

        std::fill(std::begin(m_moves), std::end(m_moves), BitBoardLayer::none());
    }

    BitBoardLayer& operator[](int fromIdx)
    {
        return m_moves[fromIdx];
    }

    const BitBoardLayer& operator[](int fromIdx) const
    {
        return m_moves[fromIdx];
    }

    template <typename FuncT>
    void forEach(FuncT&& f) const
    {
        for (int i = 0; i < Board::numPieces; ++i)
        {
            BitBoardLayer bb = m_moves[i];
            while (!bb.isEmpty())
            {
                const Square to = bb.firstSquare();
                bb.unset(to);
                f(Move(i, to));
            }
        }
    }

private:
    std::array<BitBoardLayer, Board::numPieces> m_moves;
};

Moves generateAllMovesForward(const Position& position);
void print(const Position& pos);

struct Position
{
    static Position empty(Color nextMoveColor)
    {
        return Position(nextMoveColor);
    }

    Position& operator=(const Position& other) = default;

    friend bool operator==(const Position& lhs, const Position& rhs)
    {
        return lhs.m_sideToMove == rhs.m_sideToMove && lhs.m_board == rhs.m_board;
    }

    bool hasTheSamePieces(const Position& other) const
    {
        for (int i = 0; i < numAllPieces; ++i)
        {
            if ((m_board.pieceSquare(i) == Square::none()) != (other.m_board.pieceSquare(i) == Square::none()))
            {
                return false;
            }
        }
        return true;
    }

    Piece at(Square sq) const
    {
        return m_board.at(sq);
    }

    std::uint64_t hash() const
    {
        return murmur64(*reinterpret_cast<const std::uint64_t*>(this));
    }

    void doMove(const Move& move)
    {
        m_board.doMove(move);

        m_sideToMove = oppositeColor(m_sideToMove);
    }

    void doMove(const Move& move, Piece capturedPiece)
    {
        const Square sq = m_board.pieceSquare(move.fromIdx()); // since it changes after a move is made

        doMove(move);
        if (capturedPiece.type() != PieceType::None)
        {
            place(capturedPiece, sq);
        }
    }

    void place(const Piece& piece, Square sq)
    {
        m_board.place(piece, sq);
    }

    Color sideToMove() const
    {
        return m_sideToMove;
    }

    BitBoardLayer bbByColor(Color c) const
    {
        return m_board.bbByColor(c);
    }

    BitBoardLayer bb() const
    {
        return m_board.bb();
    }

    bool hasBothKings() const
    {
        return m_board.hasBothKings();
    }

    const Board& board() const
    {
        return m_board;
    }

    BitBoardLayer bbKing(Color color) const
    {
        if (color == Color::White)
        {
            return BitBoardLayer::none() | m_board.whiteKing();
        }
        else
        {
            return BitBoardLayer::none() | m_board.blackKing();
        }
    }

    bool isInCheck(Color color) const
    {
        const BitBoardLayer bbAttack = m_board.bbAttackedByColor(oppositeColor(color));
        return (bbAttack & bbKing(color)).any();
    }

    bool isInCheck() const
    {
        return isInCheck(m_sideToMove);
    }

    bool isOpponentInCheck() const
    {
        return isInCheck(oppositeColor(m_sideToMove));
    }

    bool isCheckmate() const
    {
        if (!isInCheck())
        {
            return false;
        }

        bool checkmate = true;
        const Moves moves = generateAllMovesForward(*this);
        moves.forEach([&](Move move) {
            Position nextPos = *this;
            nextPos.doMove(move);
            if (!nextPos.isOpponentInCheck())
            {
                checkmate = false;
            }
        });

        return checkmate;
    }

    GameState gameState() const
    {
        if (!hasBothKings())
        {
            return GameState::Invalid;
        }

        if (isInCheck(oppositeColor(m_sideToMove)))
        {
            return GameState::Invalid;
        }

        if (isCheckmate())
        {
            if (m_sideToMove == Color::White)
            {
                return GameState::Loss;
            }
            else
            {
                return GameState::Win;
            }
        }

        return GameState::Valid;
    }

private:
    Board m_board;
    Color m_sideToMove;

    Position(Color c) :
        m_board{},
        m_sideToMove(c)
    {
    }
};

static_assert(sizeof(Position) == 8, "must be 8 to allow fast hash computation to work");

static constexpr int sb = sizeof(Board);
static constexpr int sp = sizeof(Position);

namespace std
{
    template<> struct hash<Position>
    {
        using argument_type = Position;
        using result_type = std::uint64_t;
        result_type operator()(const argument_type& s) const noexcept
        {
            return s.hash();
        }
    };
}

Moves generateAllMovesForward(const Position& position)
{
    MoveGenerator<PieceType::Knight> knightMoveGenerator;
    MoveGenerator<PieceType::Dabbaba> dabbabaMoveGenerator;
    MoveGenerator<PieceType::King> kingMoveGenerator;

    Moves moves;

    const Color sideToMove = position.sideToMove();

    for (int i = 0; i < Board::numPieces; ++i)
    {
        const Square sq = position.board().pieceSquare(i);
        if (sq == Square::none()) continue;

        const Piece piece = position.at(sq);
        if (piece.type() == PieceType::None || piece.color() != sideToMove)
        {
            continue;
        }

        switch (piece.type())
        {
        case PieceType::Knight:
            moves[i] = knightMoveGenerator.movesFromSquare(position.board(), sq);
            break;

        case PieceType::Dabbaba:
            moves[i] = dabbabaMoveGenerator.movesFromSquare(position.board(), sq);
            break;

        case PieceType::King:
            moves[i] = kingMoveGenerator.movesFromSquare(position.board(), sq);
            break;
        }
    }

    return moves;
}

Moves generateAllMovesBackward(const Position& position)
{
    MoveGenerator<PieceType::Knight> knightMoveGenerator;
    MoveGenerator<PieceType::Dabbaba> dabbabaMoveGenerator;
    MoveGenerator<PieceType::King> kingMoveGenerator;

    Moves moves;

    const Color sideToMove = oppositeColor(position.sideToMove());

    for (int i = 0; i < Board::numPieces; ++i)
    {
        const Square sq = position.board().pieceSquare(i);
        if (sq == Square::none()) continue;

        const Piece piece = position.at(sq);
        if (piece.type() == PieceType::None || piece.color() != sideToMove)
        {
            continue;
        }

        switch (piece.type())
        {
        case PieceType::Knight:
            moves[i] = knightMoveGenerator.movesToSquare(position.board(), sq);
            break;

        case PieceType::Dabbaba:
            moves[i] = dabbabaMoveGenerator.movesToSquare(position.board(), sq);
            break;

        case PieceType::King:
            moves[i] = kingMoveGenerator.movesToSquare(position.board(), sq);
            break;
        }
    }

    return moves;
}

struct DtmEntry
{
    using ScoreType = int;

    static DtmEntry draw()
    {
        return DtmEntry(Move::none(), 0);
    }

    static DtmEntry win()
    {
        return DtmEntry(Move::none(), std::numeric_limits<ScoreType>::max());
    }

    static DtmEntry loss()
    {
        return DtmEntry(Move::none(), std::numeric_limits<ScoreType>::min());
    }

    bool isDraw() const
    {
        return m_score == 0;
    }

    bool isWin() const
    {
        return m_score == std::numeric_limits<ScoreType>::max();
    }

    bool isLoss() const
    {
        return m_score == std::numeric_limits<ScoreType>::min();
    }

    Move nextMove() const
    {
        return m_nextMove;
    }

    ScoreType score() const
    {
        return m_score;
    }

    void setScore(ScoreType score)
    {
        m_score = score;
    }

    ScoreType dtm() const
    {
        if (isDraw()) return std::numeric_limits<ScoreType>::max();

        if (m_score > 0)
        {
            return std::numeric_limits<ScoreType>::max() - m_score;
        }
        else
        {
            return std::numeric_limits<ScoreType>::min() - m_score;
        }
    }

    void setNextMove(Move move)
    {
        m_nextMove = move;
    }

private:
    Move m_nextMove;
    ScoreType m_score;

    DtmEntry(Move move, ScoreType score) :
        m_nextMove(move),
        m_score(score)
    {
    }
};

static_assert(sizeof(DtmEntry) == 8);
static_assert(sizeof(MapType<Position, DtmEntry>::value_type) == 16);

struct PositionGenerator
{
    MapType<Position, DtmEntry> allReachable(const Position& initialPosition)
    {
        MapType<Position, DtmEntry> positions;

        auto addPosition = [&](const Position& pos, GameState gs)
        {
            switch (gs)
            {
            case GameState::Loss:
                return positions.emplace(
                    std::piecewise_construct,
                    std::forward_as_tuple(pos),
                    std::forward_as_tuple(DtmEntry::loss())
                );

            case GameState::Win:
                return positions.emplace(
                    std::piecewise_construct,
                    std::forward_as_tuple(pos),
                    std::forward_as_tuple(DtmEntry::win())
                );

            case GameState::Valid:
                return positions.emplace(
                    std::piecewise_construct,
                    std::forward_as_tuple(pos),
                    std::forward_as_tuple(DtmEntry::draw())
                );
            }
        };

        std::queue<const Position*> positionQueue;
        GameState gs = initialPosition.gameState();
        if (gs == GameState::Invalid) return positions;

        positionQueue.emplace(&initialPosition);
        addPosition(initialPosition, gs);

        int i = 0;

        while (!positionQueue.empty())
        {
            const Position& pos = *positionQueue.front();
            positionQueue.pop();

            ++i;
            if (i % reportEveryNPositions == 0)
            {
                std::cout << "Number of positions enumerated: " << i << '\n';
            }

            Moves moves = generateAllMovesForward(pos);
            moves.forEach(
                [&](const Move & move) {
                    Position nextPos = pos;
                    auto h = nextPos.board().pieces();
                    nextPos.doMove(move);
                    GameState gs = nextPos.gameState();
                    if (gs == GameState::Invalid || positions.count(nextPos) > 0)
                    {
                        return;
                    }

                    auto it = addPosition(nextPos, gs);
                    positionQueue.emplace(&(it.first->first));
                }
            );
        }

        return positions;
    }
};

struct Solver
{
    void generateDtm(MapType<Position, DtmEntry>& positions, const Position& initialPos)
    {
        std::vector<std::pair<const Position, DtmEntry>*> candidates;
        std::vector<std::pair<const Position, DtmEntry>*> nextCandidates;

        int numPositionsExactTotal = 0;
        {
            for (auto&& p : positions)
            {
                auto&& pos = p.first;
                auto&& entry = p.second;

                if (pos.hasTheSamePieces(initialPos))
                {
                    ++numPositionsExactTotal;
                }
            }
        }

        for (auto&& p : positions)
        {
            auto&& pos = p.first;
            auto&& entry = p.second;

            if (!entry.isDraw())
            {
                continue;
            }

            nextCandidates.emplace_back(&p);
        }

        int numWonPositionsTotal = 0;
        int numLostPositionsTotal = 0;
        int numWonPositionsTotalExact = 0;
        int numLostPositionsTotalExact = 0;
        for (int i = 0;;++i)
        {
            std::cout << "Started DTM = " << i + 1 << " plies ...\n";
            int numWonPositions = 0;
            int numLostPositions = 0;
            int numWonPositionsExact = 0;
            int numLostPositionsExact = 0;

            candidates = std::move(nextCandidates);
            nextCandidates = std::vector<std::pair<const Position, DtmEntry>*>{};

            std::sort(std::begin(candidates), std::end(candidates), std::less<>());
            candidates.erase(std::unique(std::begin(candidates), std::end(candidates), std::equal_to<>()), std::end(candidates));

            int j = 0;

            bool anyChange = false;
            for (auto&& p : candidates)
            {
                auto&& pos = p->first;
                auto&& entry = p->second;

                ++j;
                if (j % reportEveryNPositions == 0)
                {
                    std::cout << "\tNumber of positions examined: " << j << " of " << candidates.size() << " (" << static_cast<float>(j)/candidates.size()*100.0f << "%)\n";
                }

                Move bestNextMove = Move::none();
                DtmEntry::ScoreType bestScore = pos.sideToMove() == Color::White ? std::numeric_limits<DtmEntry::ScoreType>::min() : std::numeric_limits<DtmEntry::ScoreType>::max();
                if (!entry.isDraw())
                {
                    continue;
                }

                Moves moves = generateAllMovesForward(pos);
                moves.forEach(
                    [&](const Move & move) {
                        Position nextPos = pos;
                        nextPos.doMove(move);
                        GameState gs = nextPos.gameState();
                        if (gs == GameState::Invalid)
                        {
                            return;
                        }

                        auto it = positions.find(nextPos);
                        if (it == std::end(positions))
                        {
                            return;
                        }

                        auto& nextEntry = it->second;
                        if (!nextEntry.isDraw() && (nextEntry.dtm() > i || nextEntry.dtm() < -i))
                        {
                            return;
                        }

                        if (pos.sideToMove() == Color::White)
                        {
                            // highest score
                            if (nextEntry.score() > bestScore)
                            {
                                bestScore = nextEntry.score();
                                bestNextMove = move;
                            }
                        }
                        else
                        {
                            // lowest score
                            if (nextEntry.score() < bestScore)
                            {
                                bestScore = nextEntry.score();
                                bestNextMove = move;
                            }
                        }
                    }
                );

                if (bestNextMove == Move::none())
                {
                    continue;
                }

                const bool exact = pos.hasTheSamePieces(initialPos);

                if (bestScore > 0)
                {
                    ++numWonPositions;
                    if (exact) ++numWonPositionsExact;
                    bestScore -= 1;
                }
                else if (bestScore < 0)
                {
                    ++numLostPositions;
                    if (exact) ++numLostPositionsExact;
                    bestScore += 1;
                }

                if (bestScore == entry.score())
                {
                    continue;
                }

                anyChange = true;

                entry.setScore(bestScore);
                entry.setNextMove(bestNextMove);

                {
                    // queue up all the moves that can lead to this position

                    Moves moves = generateAllMovesBackward(pos);
                    moves.forEach(
                        [&](const Move & move) {
                            for (int i = 0; i < Board::numPieces; ++i)
                            {
                                if (initialPos.board().pieceSquare(i) != Square::none() && pos.board().pieceSquare(i) == Square::none())
                                {
                                    Position prevPos = pos;
                                    prevPos.doMove(move, Board::availablePieces[i]);
                                    GameState gs = prevPos.gameState();
                                    if (gs == GameState::Invalid)
                                    {
                                        continue;
                                    }

                                    auto it = positions.find(prevPos);
                                    if (it == std::end(positions))
                                    {
                                        continue;
                                    }

                                    nextCandidates.emplace_back(&*it);
                                }
                            }

                            Position prevPos = pos;
                            prevPos.doMove(move, Piece::none());
                            GameState gs = prevPos.gameState();
                            if (gs == GameState::Invalid)
                            {
                                return;
                            }

                            auto it = positions.find(prevPos);
                            if (it == std::end(positions))
                            {
                                return;
                            }

                            nextCandidates.emplace_back(&*it);
                        }
                    );
                }
            }

            std::cout << "Among positions with all starting pieces:\n";
            std::cout << "W/L: " << numWonPositionsExact << "/" << numLostPositionsExact << " positions\n";
            std::cout << "Among all postions:\n";
            std::cout << "W/L: " << numWonPositions << "/" << numLostPositions << " positions\n\n";
            numWonPositionsTotal += numWonPositions;
            numLostPositionsTotal += numLostPositions;
            numWonPositionsTotalExact += numWonPositionsExact;
            numLostPositionsTotalExact += numLostPositionsExact;

            if (!anyChange)
            {
                break;
            }
        }

        const int numDrawnPositionsTotalExact = numPositionsExactTotal - numWonPositionsTotalExact - numLostPositionsTotalExact;
        const int numDrawnPositionsTotal = positions.size() - numWonPositionsTotal - numLostPositionsTotal;

        std::cout << "Among positions with all starting pieces:\n";
        std::cout << "WDL: " << numWonPositionsTotalExact << ' ' << numDrawnPositionsTotalExact << ' ' << numLostPositionsTotalExact << '\n';
        std::cout << "WDL: "
            << numWonPositionsTotalExact * 100.0f / numPositionsExactTotal << "% "
            << numDrawnPositionsTotalExact * 100.0f / numPositionsExactTotal << "% "
            << numLostPositionsTotalExact * 100.0f / numPositionsExactTotal << "%\n";
        std::cout << "Among all postions:\n";
        std::cout << "WDL: " << numWonPositionsTotal << ' ' << numDrawnPositionsTotal << ' ' << numLostPositionsTotal << '\n';
        std::cout << "WDL: "
            << numWonPositionsTotal * 100.0f / positions.size() << "% "
            << numDrawnPositionsTotal * 100.0f / positions.size() << "% "
            << numLostPositionsTotal * 100.0f / positions.size() << "%\n";
    }
};

const Position* findLongestDtm(MapType<Position, DtmEntry>& positions, const Position& initialPosition)
{
    const Position* bestPos = nullptr;
    const DtmEntry* bestEntry = nullptr;
    for (auto&& [pos, entry] : positions)
    {
        if (entry.isDraw()) continue;

        if (bestEntry != nullptr && std::abs(bestEntry->dtm()) >= std::abs(entry.dtm()))
        {
            continue;
        }

        if (!pos.hasTheSamePieces(initialPosition))
        {
            continue;
        }

        bestPos = &pos;
        bestEntry = &entry;
    }

    return bestPos;
}

void print(const Position& pos)
{
    for (int y = 0; y < height; ++y)
    {
        for (int x = 0; x < width; ++x)
        {
            const Square sq(x, y);
            const Piece piece = pos.at(sq);

            if (piece == Piece(PieceType::King, Color::White)) std::cout << "K";
            else if (piece == Piece(PieceType::Knight, Color::White)) std::cout << "N";
            else if (piece == Piece(PieceType::Dabbaba, Color::White)) std::cout << "D";
            else if (piece == Piece(PieceType::King, Color::Black)) std::cout << "k";
            else if (piece == Piece(PieceType::Knight, Color::Black)) std::cout << "n";
            else if (piece == Piece(PieceType::Dabbaba, Color::Black)) std::cout << "d";
            else std::cout << ".";
        }
        std::cout << '\n';
    }
    std::cout << (pos.sideToMove() == Color::White ? "WHITE\n" : "BLACK\n");
}

int main()
{
    PositionGenerator pg;
    Position initialPos = Position::empty(Color::White);
    initialPos.place(Piece(PieceType::King, Color::White), Square(2, 0));
    initialPos.place(Piece(PieceType::Dabbaba, Color::White), Square(0, 0));
    //initialPos.place(Piece(PieceType::Dabbaba, Color::White), Square(0, 1));
    //initialPos.place(Piece(PieceType::Dabbaba, Color::White), Square(1, 0));
    //initialPos.place(Piece(PieceType::Dabbaba, Color::White), Square(1, 1));
    initialPos.place(Piece(PieceType::Knight, Color::Black), Square(width-1, height-2));
    initialPos.place(Piece(PieceType::King, Color::Black), Square(width-1, height-1));

    auto a = std::chrono::high_resolution_clock::now();
    auto positions = pg.allReachable(initialPos);
    auto b = std::chrono::high_resolution_clock::now();
    std::cout << (b - a).count() / 1000000000.0f << '\n';
    std::cout << positions.size() << '\n';
    Solver solver;
    std::chrono::high_resolution_clock::now();
    solver.generateDtm(positions, initialPos);
    std::chrono::high_resolution_clock::now();
    std::cout << (b - a).count() / 1000000000.0f << '\n';

    auto posPtr = findLongestDtm(positions, initialPos);
    if (posPtr == nullptr)
    {
        std::cout << "No mate possible\n";
        return 0;
    }

    auto pos = *posPtr;

    std::cout << positions.at(pos).dtm() << '\n';

    for (;;)
    {
        auto& entry = positions.at(pos);

        print(pos);

        auto nextMove = entry.nextMove();
        if (nextMove == Move::none())
        {
            break;
        }

        pos.doMove(nextMove);
    }
}