#include "ReadWriter.h"
#include <vector>

using namespace std;
//iostream, fstream, string included in ReadWriter.h

//Можно создавать любые классы и методы для решения задачи
//Советую разделить решение на логические блоки с комментариями
class Head;

class Node {
public:
    Node *up = nullptr;
    Node *right = nullptr;
    Node *down = nullptr;
    Node *left = nullptr;
    Head *header = nullptr;
    int i;
    int j;
};

class Head : public Node {
public:
    Head *leftHead = nullptr;
    Head *rightHead = nullptr;
    int count = 0;
    int number = 0;
};

Head **heads;
Head *rootHead;

void del(Head *head) {
    Node *currentNode = head->down;
    while (currentNode != head) {
        Node *thisNode = currentNode->right;

        do {
            //свяжем верхний и нижний между собой, без текущего
            thisNode->up->down = thisNode->down;
            thisNode->down->up = thisNode->up;
            thisNode = thisNode->right;
        } while (thisNode != currentNode);

        currentNode = currentNode->down;
    }

    head->rightHead->leftHead = head->leftHead;
    head->leftHead->rightHead = head->rightHead;
}

void put(Head *head) {
    Node *currentNode = head->up;
    while (currentNode != head) {
        Node *thisNode = currentNode->left;

        do {
            //добавим текущий в эту систему
            thisNode->up->down = thisNode;
            thisNode->down->up = thisNode;
            thisNode = thisNode->left;
        } while (thisNode != currentNode);

        currentNode = currentNode->up;
    }

    head->rightHead->leftHead = head;
    head->leftHead->rightHead = head;
}

void build(char **matrix, int n, int m) {
    //создаем нашу матрицу
    Node ***res = new Node **[n];
    heads = new Head *[n];
    for (int i = 0; i < n; ++i) {
        res[i] = new Node *[m];
        for (int j = 0; j < m; ++j)
            res[i][j] = nullptr;
    }
    //читаем данные и создаем ноды
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j)
            if (matrix[i][j] == '1') {
                Node *node = new Node();
                node->i = i;
                node->j = j;
                res[i][j] = node;
            }
    }

    //установим хедеры
    for (int j = 0; j < m; ++j) {
        Head *newHead = new Head();
        newHead->number = j;
        heads[j] = newHead;

        //ищем нижний элемент
        int nowI = 0, nowJ = j;
        while (true) {
            if (res[nowI][nowJ] != nullptr) {
                newHead->down = res[nowI][nowJ];
                res[nowI][nowJ]->up = newHead;
                break;
            }
            ++nowI;
        }

        //ищем верхний элемент
        nowI = n - 1;
        while (true) {
            if (res[nowI][nowJ] != nullptr) {
                newHead->up = res[nowI][nowJ];
                res[nowI][nowJ]->down = newHead;
                break;
            }
            --nowI;
        }
    }

    //соединяем хеды между собой
    rootHead = new Head();
    rootHead->number = -1;
    for (int i = 1; i < m - 1; i++) {
        Head *head = heads[i];
        head->leftHead = heads[i - 1];
        head->rightHead = heads[i + 1];
    }
    heads[0]->rightHead = heads[1];
    heads[0]->leftHead = rootHead;
    rootHead->rightHead = heads[0];

    heads[m - 1]->rightHead = rootHead;
    rootHead->leftHead = heads[m - 1];
    heads[m - 1]->leftHead = heads[m - 2];


    //Задаем связи
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            //для каждого элемента

            if (res[i][j] != nullptr) {

                res[i][j]->header = heads[j];

                //Устанавливаем right
                int nowI = i;
                int nowJ = j + 1;
                while (true) {
                    if (nowJ == m)
                        nowJ = 0;
                    if (res[nowI][nowJ] != nullptr) {
                        res[i][j]->right = res[nowI][nowJ];
                        break;
                    }
                    ++nowJ;
                }

                //Устанавливаем left
                nowJ = j - 1;
                while (true) {
                    if (nowJ == 0)
                        nowJ = m;
                    if (res[nowI][nowJ] != nullptr) {
                        res[i][j]->left = res[nowI][nowJ];
                        break;
                    }
                    --nowJ;
                }

                //Устанавливаем down
                if (res[i][j]->down == nullptr) {
                    nowI = i + 1;
                    nowJ = j;
                    while (true) {
                        if (nowI == n)
                            nowI = 0;
                        if (res[nowI][nowJ] != nullptr) {
                            res[i][j]->down = res[nowI][nowJ];
                            break;
                        }
                        ++nowI;
                    }
                }

                //Устанавливаем up
                if (res[i][j]->up == nullptr) {
                    nowI = i - 1;
                    while (true) {
                        if (nowI == -1)
                            nowI = n - 1;
                        if (res[nowI][nowJ] != nullptr) {
                            res[i][j]->up = res[nowI][nowJ];
                            break;
                        }
                        --nowI;
                    }
                }
            }
        }
    }
    cout << "build";
}

vector<Node *> solution = vector<Node *>();

//счетчик скрытых столбцов
int coveredColumns = 0;
int maxColumns = 0;

bool findSolution() {
    if (coveredColumns == maxColumns)
        return true;
    Head *h = rootHead->rightHead;
    if (h->down != h) {
        Node *n = h->down;

        while (n != h) {
            del(h);
            coveredColumns++;
            solution.push_back(n);
            for (Node *j = n->right; j != n; j = j->right) {
                del(j->header);
                coveredColumns++;
            }

            if (findSolution())
                return true;
            solution.pop_back();
            for (Node *j = n->left; j != n; j = j->left) {
                put(j->header);
                coveredColumns--;
            }


            put(h);
            coveredColumns--;
            n = n->down;
        }
    }
    return false;
};

//Основной метод решения задачи, параметры:
//matrix - матрица NxM, представленная как N массивов по строкам, в каждом по M элементов '0' или '1'
//n, m - размеры матрицы
//result - массив для вывода решения, содержит строки из матрицы,
//для него надо выделить память здесь, передается по ссылке, чтобы можно было изменить указатель и получить это значение из main
//resultSize - количество строк в результате, передается по ссылке, чтобы можно было получить значение из main
void solve(char **matrix, int n, int m, char **&result, int &resultSize) {
    //Можно создавать любые классы и методы для решения задачи
    //Советую разделить решение на логические блоки с комментариями
    maxColumns = m;
    build(matrix, n, m);
    findSolution();

    resultSize = solution.size();

    result = new char *[resultSize];
    for (int i = 0; i < resultSize; i++) {
        result[i] = new char[m];
        for (int j = 0; j < m; j++)
            result[i][j] = '0';

        int index = solution[i]->i;
        for (int j = 0; j < m; j++)
            result[i][j] = matrix[index][j];
    }

}


int main() {
    ReadWriter rw;
    //читаем параметры
    int n, m;
    rw.readInts(n, m);

    char **matrix = new char *[n];
    for (int i = 0; i < n; i++)
        matrix[i] = new char[m];
    //читаем матрицу
    rw.readMatrix(matrix, n, m);

    //Память под result не выделяется здесь, так как неизвестно какое количество строк войдет в решение
    //Предлагается выделить память прямо в методе solve
    int resultSize = 0; //количество строк в решении
    char **result = nullptr;
    solve(matrix, n, m, result, resultSize);

    //выводим результат в файл
    rw.writeInts(resultSize, m);
    rw.writeMatrix(result, resultSize, m);

    //освобождаем память матрицы, которую выделяли здесь
    for (int i = 0; i < n; i++)
        delete[] matrix[i];
    delete[] matrix;

    //освобождаем память массива результата, которая здесь не выделялась...
    for (int i = 0; i < resultSize; i++)
        delete[] result[i];
    delete[] result;

    return 0;
}