#include <iostream>
#include <fstream>
#include <thread>
#include <vector>
#include <chrono>
#include <sstream>
#include <math.h>
#include <cassert>
#include <mutex>
#include <condition_variable>
#include <array>

using namespace std;

class Tile {
    bool was;
    bool is;
    int step;
public:
    Tile(bool what) : was(false), is(what), step(0) {};

    void newState(bool state) {
        this->was = this->is;
        this->is = state;
        this->step++;
    }

    void update() {
        this->was = this->is;
        this->step++;
    }

    int getStep() {
        return this->step;
    }

    bool getWas() {
        return this->was;
    }

    bool getIs() {
        return this->is;
    }
};

int N, T, S, height, width;
vector<Tile> field;
vector<int> stepcounter;
vector<bool> alarmclock;
mutex Mutex;
condition_variable cv;

ifstream fin("C:\\clionfolder\\prog5\\input.txt");
ofstream fout("C:\\clionfolder\\prog5\\output.txt");

void input() {
    int temp;
    fin >> N >> T >> S;
    for (int i = 0; i < N * N; i++) {
        fin >> temp;
        field.emplace_back(temp);
    }
}

int moveInField(int horiz, int vertic, int id, int direction) {
    int x = id / horiz;
    int y = id % horiz;
    switch (direction) {
        case (0): {                 //up
            x--;
            if (x < 0) {
                x = vertic - 1;
            }
            break;
        }
        case (1): {                 //right
            y++;
            if (y == horiz) {
                y = 0;
            }
            break;
        }
        case (2): {                 //down
            x++;
            if (x == vertic) {
                x = 0;
            }
            break;
        }
        case (3): {                 //left
            y--;
            if (y < 0) {
                y = horiz - 1;
            }
            break;
        }
    }
    return x * horiz + y;
}

int defineThreadCoverage() {
    //Каждый тред покрывает прямоугольник i x (N*N/T/i) для оптимизации числа соседей.
    int temp = N * N / T;   //число клеток на один тред
    if (N % T == 0) {       //Если получится разбить на "полосы", то у каждой зоны всего две соседних
        return N / T;
    } else {
        for (int i = (int) sqrt(temp); i > 0; i--) {
            if (temp % i == 0) {
                if (N % i == 0 && N % (temp / i) == 0) {
                    return i;
                }
            }
        }
    }
    throw ("Error");
}

int zoneId(int TileId) {
    int x = TileId / N;
    int y = TileId % N;
    x = x / height;
    y = y / width;
    return x * (N / width) + y;
}

bool goodToGo(int id, array<int, 8> &neighbours) {
    //id-ый тред покрывает клетки с [(id / horiz) * vertic][(id % horiz) * horiz] по [(id / horiz) * vertic + height - 1][(id % horiz) * horiz + width - 1]
    int curstep = stepcounter[id];
    bool result = true;
    Mutex.lock();
    for (int i:neighbours) {
        if (stepcounter[i] < curstep) {
            result = false;
        }
    }
    Mutex.unlock();
    return result;
}

void lookForNeighbours(int tileNumber, array<int, 8> &neighbours,int horiz, int vertic) {
    for (int i = 0; i < 8; i++) {
        neighbours[i] = moveInField(horiz, vertic, tileNumber, i % 4);
    }
    for (int i = 0; i < 4; i++) {
        neighbours[i] = moveInField(horiz, vertic, neighbours[i], (i + 1) % 4);
    }
}

int neighboursAlive(int tileNumber) {
    int alive = 0;
    int curstep = stepcounter[zoneId(tileNumber)];
    array<int, 8> neighbours;
    lookForNeighbours(tileNumber,neighbours,N,N);
    for (int i:neighbours) {
        Mutex.lock();
        assert(field[i].getStep() == curstep || field[i].getStep() == curstep + 1);
        if (field[i].getStep() == curstep) {
            if (field[i].getIs()) {
                alive++;
            }
        } else {
            if (field[i].getWas()) {
                alive++;
            }
        }
        Mutex.unlock();
    }
    return alive;
}

void ThreadBody(int id) {
    array<int, 8> neighbours;
    int horiz = N / width;
    int vertic = N / height;
    lookForNeighbours(id, neighbours,horiz,vertic);
    for (int COUNTER = 0; COUNTER < S; COUNTER++) {
        while (!goodToGo(id, neighbours)) {
            std::unique_lock<std::mutex> lk(Mutex);
            alarmclock[id] = false;
            cv.wait(lk, [id] { return alarmclock[id]; });
            lk.unlock();
        }
        int tileNumber, aliveNeighbours;
        //Здесь всё просто, для каждой клетки проверяем условие по соседям и шенаниганы из условия выполняем
        for (int i = (id / horiz) * height; i < (id / horiz + 1) * height; i++) {
            for (int j = (id % horiz) * width; j < (id % horiz + 1) * width; j++) {
                tileNumber = i * N + j;
                bool state = field[tileNumber].getIs();
                aliveNeighbours = neighboursAlive(tileNumber);
                Mutex.lock();
                if (state && (aliveNeighbours < 2 || aliveNeighbours > 3)) {
                    field[tileNumber].newState(false);
                } else if (!state && aliveNeighbours == 3) {
                    field[tileNumber].newState(true);
                } else {
                    field[tileNumber].update();
                }
                Mutex.unlock();
            }
        }
        stepcounter[id]++;
        Mutex.lock();
        for(int i : neighbours){
            alarmclock[i] = true;
        }
        Mutex.unlock();
        cv.notify_one();
        /*ostringstream out;
        out << "Thread with id " << id << " started\n";
        cout << out.str();

        out.str("");
        out << "Thread with id " << id << " finished\n";
        cout << out.str();  */
    }

}

void output() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (field[i * N + j].getIs()) {
                cout << "1 ";
            } else {
                cout << "0 ";
            }
        }
        cout << endl;
    }
}

int main() {
    input();
    output();
    cout << endl;
    this_thread::sleep_for(1ms);
    vector<thread> ThreadPile;
    height = defineThreadCoverage();    //высота покрываемой зоны
    width = N * N / T / height;         //ширина покрываемой зоны
    for (int i = 0; i < T; i++) {
        stepcounter.push_back(0);
        alarmclock.push_back(false);
    }
    for (int i = 0; i < T; i++) {
        ThreadPile.emplace_back(ThreadBody, i);
    }
    for (int i = 0; i < T; i++) {
        if (ThreadPile[i].joinable()) {
            ThreadPile[i].join();
        }
    }
    output();
    return 0;
}