#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <queue>
#include <vector>
#include <string.h>
#include <math.h>
#include <chrono>
#include <random>
#include <time.h>
#include <map>
using namespace std;

const int MAXN = 302;
const int MAXP = 10;

mt19937 mt(1337);

int n, d, p;
int R;
int field[MAXN][MAXN];
int result[MAXN][MAXN];
int HERO;

namespace Timing
{
    long long totalTime = 0;
    auto start = chrono::high_resolution_clock::now();

    void resetClock()
    {
        totalTime = 0;
    }

    void startClock()
    {
        start = chrono::high_resolution_clock::now();
    }

    void stopClock()
    {
        auto finish = chrono::high_resolution_clock::now();
        totalTime += std::chrono::duration_cast<std::chrono::nanoseconds>(finish-start).count();
    }

    long long getClock()
    {
        return totalTime / 1000000;
    }

    void showClock()
    {
        fprintf(stderr, "Time: %lld\n", totalTime / 1000000);
    }
}

bool TimeIsOK(double limit=4.0)
{
    return (double)clock() / (double)CLOCKS_PER_SEC < limit;
}

const pair<int, int> NBOFFS[] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int pathicFill(int x, int y, int regNum, int dir, int minX, int minY, int maxX, int maxY)
{
    int ctr = 0;
    int heroCounts[MAXP];
    int wins = 0;
    memset(heroCounts, 0, sizeof(heroCounts));

    while(x <= maxX)
    {
        result[x][y] = regNum;
        ctr++;

        heroCounts[ field[x][y] ]++;

        if (ctr == R)
        {
            ctr = 0;
            regNum++;

            bool winner = true;
            for (int i = 1; i <= p; i++)
            {
                if (i != HERO && heroCounts[i] >= heroCounts[HERO])
                    winner = false;
            }

            if (winner)
                wins++;

            memset(heroCounts, 0, sizeof(heroCounts));
        }

        y += dir;
        if (y < minY || y > maxY || result[x][y] != 0)
        {
            y -= dir;
            x++;
            dir *= -1;
        }
    }

    return wins;
}

///

bool activeRegion[MAXN][MAXN];
int color[MAXN][MAXN];
int colorCnt[10];
int UTFO[MAXN][MAXN];
int Key = 1;
int pCounts[MAXP];
int totalCounts[MAXP];
int H, W;

bool OK(int x, int y, bool expectedActive=true)
{
    if (x < 1 || y < 1 || x > H || y > W)
        return false;
    return activeRegion[x][y] == expectedActive;
}

int getSize(int x, int y)
{
    if (!OK(x, y) || UTFO[x][y] == Key)
        return 0;
    UTFO[x][y] = Key;

    int ans = 1;
    ans += getSize(x+1, y);
    ans += getSize(x-1, y);
    ans += getSize(x, y+1);
    ans += getSize(x, y-1);

    return ans;
}

bool canRemove(int x, int y, int curSize)
{
    assert(activeRegion[x][y]);

    int nbCount = 0;
    int goodCorners = 0;
    for (int i = 0; i < 4; i++)
    {
        auto [cx, cy] = NBOFFS[i];

        if (OK(x + cx, y + cy))
            nbCount++;

        int X1 = x + cx;
        int Y1 = y + cy;

        if (!OK(X1, Y1))
            continue;

        for (int j = i + 1; j < 4; j++)
        {
            auto [cx2, cy2] = NBOFFS[j];

            int X2 = x + cx2;
            int Y2 = y + cy2;

            if (!OK(X2, Y2))
                continue;

            if (X1 == X2 || Y1 == Y2)
                continue;

            if (activeRegion[X1][Y2] && activeRegion[X2][Y1])
                goodCorners++;
        }
    }

    if (goodCorners >= nbCount - 1)
        return true;

    return false;
}

bool quickDrop(int x, int y)
{
    int nbCount = 0;
    int goodCorners = 0;
    for (int i = 0; i < 4; i++)
    {
        auto [cx, cy] = NBOFFS[i];

        int X1 = x + cx;
        int Y1 = y + cy;

        if (!OK(X1, Y1, false))
            continue;

        if (color[X1][Y1] != color[x][y])
            continue;

        nbCount++;

        for (int j = i + 1; j < 4; j++)
        {
            auto [cx2, cy2] = NBOFFS[j];

            int X2 = x + cx2;
            int Y2 = y + cy2;

            if (!OK(X2, Y2, false))
                continue;
            if (X1 == X2 || Y1 == Y2)
                continue;
            if (color[X2][Y2] != color[x][y])
                continue;

            if (!activeRegion[X1][Y2] && !activeRegion[X2][Y1] && color[X1][Y2] == color[x][y] && color[X2][Y1] == color[x][y])
                goodCorners++;
        }
    }

    if (goodCorners >= nbCount - 1)
        return true;

    return false;
}

priority_queue<pair<pair<int, int>, pair<int, int>>> erosionQ[MAXP];
pair<int, int> erOrder[MAXP];
bool inQ[MAXN][MAXN];

void qAddActiveNbs(int realX, int realY, int offX, int offY)
{
    int X = realX - offX + 1;
    int Y = realY - offY + 1;

    for (auto [cx, cy] : NBOFFS)
    {
        int nX = X + cx;
        int nY = Y + cy;

        if (OK(nX, nY) && !inQ[nX][nY])
        {
            int fieldVal = field[realX + cx][realY + cy];

            inQ[nX][nY] = true;

            int pr = 0;

            int avgCnt = 0;
            for (auto [cx2, cy2] : NBOFFS)
            {
                int prX = nX + cx2;
                int prY = nY + cy2;

                if (OK(prX, prY))
                {
                    avgCnt++;
                    int otherVal = field[prX + offX - 1][prY + offY - 1];
                    if (otherVal != HERO)
                        pr += pCounts[otherVal];
                }
            }
            pr /= avgCnt;

            erosionQ[fieldVal].push({{pr, color[X][Y]}, {nX, nY}});
        }
    }
}

int solveRegion(int x1, int y1, int x2, int y2, int numCols, bool specialMode=false, bool superSpecialMode=false)
{
    int totalSize = 0;

    H = x2 - x1 + 1;
    W = y2 - y1 + 1;
    memset(pCounts, 0, sizeof(pCounts));
    memset(totalCounts, 0, sizeof(totalCounts));
    memset(colorCnt, 0, sizeof(colorCnt));

    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if ( (i > 1 && i < H && j > 1 && j < W && !specialMode) || (i > 1 && specialMode) )
            {
                activeRegion[i][j] = true;
                totalSize++;
            }
            else
            {
                int id = 0;
                if (i == 1)
                    id = j - 1;
                else if (j == W)
                    id = (W - 1) + (i - 1);
                else if (i == H)
                    id = (W - 1) + (H - 1) + (W - j);
                else
                    id = 2 * (W - 1) + (H - 1) + (H - i);

                int clr = numCols * id / (2 * (H + W - 2)) + 1;

                color[i][j] = clr;
                colorCnt[clr]++;

                activeRegion[i][j] = false;
            }

            inQ[i][j] = false;
        }
    }

    for (int i = x1; i <= x2; i++)
    {
        for (int j = y1; j <= y2; j++)
        {
            totalCounts[ field[i][j] ]++;
            if (activeRegion[i - x1 + 1][j - y1 + 1])
                pCounts[ field[i][j] ]++;
        }
    }

    /*fprintf(stderr, "Starting\n");
    for (int i = 1; i <= p; i++)
    {
        fprintf(stderr, "Count[%d] = %d\n", i, pCounts[i]);
    }*/

    for (int i = 1; i <= p; i++)
    {
        while(!erosionQ[i].empty())
            erosionQ[i].pop();
    }

    for (int i = x1; i <= x2; i++)
    {
        for (int j = y1; j <= y2; j++)
        {
            int X = i - x1 + 1;
            int Y = j - y1 + 1;

            if (!activeRegion[X][Y])
                qAddActiveNbs(i, j, x1, y1);
        }
    }

    Timing::startClock();
    bool firstLowRoll = true;
    while(totalSize > R)
    {
        //fprintf(stderr, "%d vs %d\n", pCounts[HERO], pCounts[1]);
        for (int i = 1; i <= p; i++)
        {
            if (i == HERO)
                erOrder[i] = {-20, i};
            else
                erOrder[i] = {pCounts[i] - pCounts[HERO], i};

            if (superSpecialMode)
            {
                int oCount = totalCounts[i] - pCounts[i];
                int oCountHero = totalCounts[HERO] - pCounts[HERO];

                bool hasToSpare = true;
                for (int j = 1; j <= p; j++)
                {
                    if (j == HERO)
                        continue;
                    if (pCounts[j] >= pCounts[HERO] - 1)
                        hasToSpare = false;
                }

                if (hasToSpare)
                {
                    if (i == HERO)
                        erOrder[i] = {999999, i};
                    else
                        erOrder[i] = {oCount - oCountHero, i};
                }
            }
        }
        sort(erOrder+1, erOrder+1+p);
        reverse(erOrder+1, erOrder+1+p);

        int bestX = -1;
        int bestY = -1;
        int bestCost = -1;
        int bestCol;
        for (int i = 1; i <= p; i++)
        {
            int ind = erOrder[i].second;
            if (!erosionQ[ind].empty())
            {
                auto [pr, pos] = erosionQ[ind].top();
                auto [prior, col] = pr;
                erosionQ[ind].pop();

                bestX = pos.first;
                bestY = pos.second;
                bestCost = erOrder[i].first;
                bestCol = col;
                break;
            }
        }
        if (bestX == -1)
            return false;

        if (!canRemove(bestX, bestY, totalSize))
        {
            inQ[bestX][bestY] = false;
            continue;
        }

        int bestVal = field[bestX + x1 - 1][bestY + y1 - 1];
        activeRegion[bestX][bestY] = false;
        color[bestX][bestY] = bestCol;
        colorCnt[bestCol]++;
        pCounts[bestVal]--;
        totalSize--;

        //fprintf(stderr, "Drop %d [real cost %d vs expected %d]\n", bestVal, pCounts[bestVal] - pCounts[HERO], bestCost);

        qAddActiveNbs(bestX + x1 - 1, bestY + y1 - 1, x1, y1);
    }
    Timing::stopClock();

    ///Color-sync
    if (numCols > 1)
    {
        bool change = true;
        while(change)
        {
            change = false;
            for (int i = 1; i <= H; i++)
            {
                for (int j = 1; j <= W; j++)
                {
                    if (activeRegion[i][j])
                        continue;

                    if (colorCnt[ color[i][j] ] > R && quickDrop(i, j))
                    {
                        for (auto [cx, cy] : NBOFFS)
                        {
                            int nx = i + cx, ny = j + cy;

                            if (!OK(nx, ny, false))
                                continue;

                            if (colorCnt[ color[nx][ny] ] < R)
                            {
                                colorCnt[ color[i][j] ]--;
                                color[i][j] = color[nx][ny];
                                colorCnt[ color[nx][ny] ]++;

                                change = true;

                                break;
                            }
                        }
                    }
                }
            }
        }
    }

    /*for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (activeRegion[i][j])
                fprintf(stderr, "%d", field[i + x1 - 1][j + y1 - 1]);
            else
            {
                fprintf(stderr, "%c", 'A' + color[i][j] - 1);
            }
            //printf("%d", (int)activeRegion[i][j]);
        }
        fprintf(stderr, "\n");
    }
    fprintf(stderr, "\n");*/

    /*
    for (int i = 1; i <= numCols; i++)
    {
        fprintf(stderr, "Color %d: %d\n", i, colorCnt[i]);
    }
    fprintf(stderr, "\n");
    */

    //fprintf(stderr, "%d / %d\n", pCounts[HERO], R);
    /*fprintf(stderr, "Final\n");
    for (int i = 1; i <= p; i++)
    {
        fprintf(stderr, "Count[%d] = %d\n", i, pCounts[i]);
    }*/

    for (int i = 1; i <= numCols; i++)
    {
        if (colorCnt[i] != R)
            return 0;
    }

    for (int i = 1; i <= p; i++)
    {
        if (i != HERO && pCounts[i] >= pCounts[HERO])
        {
            //fprintf(stderr, "F because of %d having %d\n", i, pCounts[i]);
            return 0;
        }
    }

    bool inverseWin = true;
    for (int i = 1; i <= p; i++)
    {
        if (i != HERO && (totalCounts[i] - pCounts[i]) >= (totalCounts[HERO] - pCounts[HERO]))
        {
            inverseWin = false;
            break;
        }
    }

    /*static int invwins = 0;
    if (inverseWin)
    {
        invwins++;
        fprintf(stderr, "INVERSE WON %d!\n", invwins);
    }*/

    return 1 + (int)inverseWin;
}


namespace Verification
{
    int UTFO[MAXN][MAXN];
    int Key = 1;

    int DFS(int x, int y, int reg, int res[MAXN][MAXN])
    {
        if (x < 1 || y < 1 || x > n || y > n)
            return 0;
        if (UTFO[x][y] == Key || res[x][y] != reg)
            return 0;
        UTFO[x][y] = Key;

        int sz = 1;
        for (auto [cx, cy] : NBOFFS)
        {
            sz += DFS(x + cx, y + cy, reg, res);
        }

        return sz;
    }

    void printField(int res[MAXN][MAXN])
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                printf("%d", res[i][j] % 10);
            }
            printf("\n");
        }
    }

    void verify(int res[MAXN][MAXN])
    {
        map<int, pair<int, int>> seen;

        Key++;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (UTFO[i][j] == Key)
                    continue;

                if (res[i][j] < 1 || res[i][j] > d)
                {
                    fprintf(stderr, "Invalid region %d at %d,%d\n", res[i][j], i, j);
                    printField(res);
                    exit(1);
                }

                int sz = DFS(i, j, res[i][j], res);

                if (sz != R)
                {
                    fprintf(stderr, "Invalid region size of region %d started at %d,%d - found %d and expected %d\n", res[i][j], i, j, sz, R);
                    printField(res);
                    exit(1);
                }

                if (seen.find(res[i][j]) != seen.end())
                {
                    auto it = seen.find(res[i][j]);
                    auto [px, py] = (*it).second;
                    fprintf(stderr, "Region %d encountered more than once - at %d,%d and %d,%d\n", res[i][j], i, j, px, py);
                    printField(res);
                    exit(1);
                }
                seen.insert({res[i][j], {i, j}});
            }
        }
    }
}

namespace SpiralBuddy
{
    int voteCounts[511][MAXP];
    bool spiralCovered[MAXN][MAXN];
    int fixDir[MAXN][MAXN];
    bool added[MAXN][MAXN];

    inline bool ofRegion(int x, int y, int reg)
    {
        return x >= 1 && y >= 1 && x <= n && y <= n && result[x][y] == reg;
    }

    bool locallySafe(int x, int y, bool debug=false)
    {
        int nbCount = 0;
        int goodCorners = 0;
        for (int i = 0; i < 4; i++)
        {
            auto [cx, cy] = NBOFFS[i];

            int X1 = x + cx;
            int Y1 = y + cy;

            if (!ofRegion(X1, Y1, result[x][y]))
                continue;

            nbCount++;

            for (int j = i + 1; j < 4; j++)
            {
                auto [cx2, cy2] = NBOFFS[j];

                int X2 = x + cx2;
                int Y2 = y + cy2;

                if (!ofRegion(X2, Y2, result[x][y]))
                    continue;
                if (X1 == X2 || Y1 == Y2)
                    continue;

                if (result[X1][Y2] == result[x][y] && result[X2][Y1] == result[x][y])
                    goodCorners++;
            }
        }

        return goodCorners >= nbCount - 1;
    }

    inline bool hasNb(int x, int y, int reg)
    {
        for (auto [cx, cy] : NBOFFS)
        {
            if (ofRegion(x + cx, y + cy, reg))
                return true;
        }
        return false;
    }

    int solveSpiral(int W)
    {
        vector< pair<int, int> > spiral;
        vector<int> spiralTangent;
        vector< pair<int, int> > blocks;
        int bX = 1, bY = 1;
        int dir = 1;

        memset(voteCounts, 0, sizeof(voteCounts));
        memset(spiralCovered, false, sizeof(spiralCovered));
        memset(added, false, sizeof(added));
        memset(result, 0, sizeof(result));

        while(true)
        {
            //fprintf(stderr, "%d %d with dir %d\n", bX, bY, dir);
            spiral.push_back({bX, bY});
            spiralTangent.push_back((dir + 1) % 4);

            spiralCovered[bX][bY] = true;

            int regDir = (dir + 1) % 4;
            int rx = bX, ry = bY;
            rx += NBOFFS[regDir].first;
            ry += NBOFFS[regDir].second;


            bX += NBOFFS[dir].first;
            bY += NBOFFS[dir].second;

            if (bX < 1 || bX > n || bY < 1 || bY > n || added[bX][bY] || spiralCovered[bX][bY])
            {
                //fprintf(stderr, "Rolling back at %d %d with grid %c\n", bX, bY, grid[bX][bY]);
                bX -= NBOFFS[dir].first;
                bY -= NBOFFS[dir].second;

                dir = (dir + 1) % 4;

                bX += NBOFFS[dir].first;
                bY += NBOFFS[dir].second;

                if (bX < 1 || bX > n || bY < 1 || bY > n || added[bX][bY] || spiralCovered[bX][bY])
                    break;
            }
            else
            {
                for (int i = 1; i <= W; i++)
                {
                    assert(rx >= 1 && rx <= n && ry >= 1 && ry <= n);
                    if (spiralCovered[rx][ry])
                        break;
                    if (!added[rx][ry])
                    {
                        blocks.push_back({rx, ry});
                        added[rx][ry] = true;
                    }
                    fixDir[rx][ry] = (regDir + 2) % 4;

                    rx += NBOFFS[regDir].first;
                    ry += NBOFFS[regDir].second;
                }
            }
        }

        int curSpiralRegSize = 0;
        int spiralRegId = -1;

        int blockPtr = 0;
        int spiralPtr = 0;
        int winners = 0;
        for (int reg = 1;;reg++)
        {
            //fprintf(stderr, "Solving region %d\n", reg);

            if (blockPtr + R > blocks.size())
            {
                while(spiralPtr < spiral.size())
                {
                    auto [x, y] = spiral[spiralPtr];
                    result[x][y] = spiralRegId;
                    spiralCovered[x][y] = true;
                    spiralPtr++;

                    curSpiralRegSize++;
                    if (curSpiralRegSize == R)
                    {
                        curSpiralRegSize = 0;
                        spiralRegId--;
                    }
                }

                while(blockPtr < blocks.size())
                {
                    auto [x, y] = blocks[blockPtr];
                    result[x][y] = spiralRegId;
                    spiralCovered[x][y] = true;
                    blockPtr++;

                    curSpiralRegSize++;
                    if (curSpiralRegSize == R)
                    {
                        curSpiralRegSize = 0;
                        spiralRegId--;
                    }
                }

                break;
            }

            for (int i = 1; i <= R; i++)
            {
                auto [x, y] = blocks[blockPtr];
                result[x][y] = reg;

                voteCounts[reg][ field[x][y] ]++;

                blockPtr++;
            }

            while(spiralPtr < spiral.size())
            {
                auto [x, y] = spiral[spiralPtr];
                int tangent = spiralTangent[spiralPtr];
                x += NBOFFS[tangent].first;
                y += NBOFFS[tangent].second;

                //fprintf(stderr, "Result is %d\n", result[x][y]);

                if (!spiralCovered[x][y] && result[x][y] == 0) /// Too far
                    break;

                result[ spiral[spiralPtr].first ][ spiral[spiralPtr].second ] = spiralRegId;

                int colSize = 1;

                vector< pair<int, int> > considered;
                considered.push_back({x, y});
                while(!considered.empty())
                {
                    auto [x, y] = considered.back();
                    considered.pop_back();

                    if (curSpiralRegSize + colSize == R)
                        break;
                    if (spiralCovered[x][y])
                        continue;
                    if (result[x][y] != reg)
                        continue;
                    if (blockPtr >= blocks.size())
                        break;
                    if (!locallySafe(x, y))
                        continue;

                    auto [bx, by] = blocks[blockPtr];

                    result[x][y] = 0;
                    bool newIsFine = hasNb(bx, by, reg);
                    result[x][y] = reg;

                    if (!newIsFine)
                        continue;

                    int val = field[x][y];
                    if (val != HERO && voteCounts[reg][val] >= voteCounts[reg][HERO])
                    {
                        spiralCovered[x][y] = true;
                        result[x][y] = spiralRegId;
                        colSize++;

                        voteCounts[reg][val]--;


                        result[bx][by] = reg;
                        voteCounts[reg][ field[bx][by] ]++;

                        blockPtr++;
                    }
                    else
                        continue;

                    int nx = x + NBOFFS[tangent].first;
                    int ny = y + NBOFFS[tangent].second;
                    considered.push_back({nx, ny});

                    nx = x + NBOFFS[(tangent+1)%4].first;
                    ny = y + NBOFFS[(tangent+1)%4].second;
                    considered.push_back({nx, ny});

                    nx = x + NBOFFS[(tangent+3)%4].first;
                    ny = y + NBOFFS[(tangent+3)%4].second;
                    considered.push_back({nx, ny});
                }

                if (curSpiralRegSize + colSize == R)
                {
                    curSpiralRegSize = 0;
                    spiralRegId--;
                }
                else
                    curSpiralRegSize += colSize;

                spiralPtr++;
            }

            bool winner = true;
            //fprintf(stderr, "Region finished:\n");
            for (int i = 1; i <= p; i++)
            {
                if (i != HERO && voteCounts[reg][i] >= voteCounts[reg][HERO])
                    winner = false;
                //fprintf(stderr, "%d ", voteCounts[reg][i]);
            }
            //fprintf(stderr, "\n");

            if (winner)
                winners++;
        }

        //fprintf(stderr, "Expected winners: %d\n", winners);
        //fprintf(stderr, "Final spiral size: %d\n", curSpiralRegSize);
        assert(curSpiralRegSize == 0);

        int maxReg = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (!spiralCovered[i][j])
                    maxReg = max(maxReg, result[i][j]);
            }
        }

        //fprintf(stderr, "%d / %d won\n", winners, maxReg);

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (spiralCovered[i][j])
                    result[i][j] = maxReg + abs(result[i][j]);
            }
        }

        /*for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (spiralCovered[i][j])
                    printf("#");
                else
                    printf("%d", result[i][j]%10);
            }
            printf("\n");
        }
        exit(1);*/

        return winners;
    }
}


int cnt[MAXP];

int remResult[MAXN][MAXN];
int bestSucc;

double solveCase(int hero)
{
    HERO = hero;
    memset(result, 0, sizeof(result));

    bestSucc = pathicFill(1, 1, 1, 1, 1, 1, n, n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            remResult[i][j] = result[i][j];
        }
    }

    int lastSucc = 0;
    int loseStreak = 0;
    for (int i = 2; i <= 80; i++)
    {
        if (i >= n)
            break;
        if (bestSucc >= d - 1)
            break;
        if (!TimeIsOK())
            break;

        int curSucc = SpiralBuddy::solveSpiral(i);
        //fprintf(stderr, "W=%d -- %d\n", i, curSucc);
        //Verification::verify(result);

        if (curSucc < d / 3 && i > 5)
            break;
        if (curSucc == 0)
            break;

        if (curSucc < lastSucc)
        {
            loseStreak++;
            if (loseStreak > 3)
                break;
        }
        lastSucc = curSucc;

        if (curSucc > bestSucc)
        {
            bestSucc = curSucc;

            for (int j = 1; j <= n; j++)
            {
                for (int in = 1; in <= n; in++)
                {
                    remResult[j][in] = result[j][in];
                }
            }
        }
    }

    for (int C = 1; C <= 6; C++)
    {
        if (HERO == 1 && C > 1)
            break;

        memset(result, 0, sizeof(result));

        if (!TimeIsOK())
            break;

        int GOAL = (C + 1) * R;

        int H = (int)floor(sqrt(GOAL));
        int W = GOAL / H;
        int succ = 0;

        while(H * W != GOAL)
        {
            H--;
            W = GOAL / H;
        }

        for (int i = 15; i * i <= GOAL; i++)
        {
            int curH = i;
            int curW = GOAL / i;

            if (GOAL % i == 0 && (n / H) * (n / W) < (n / curH) * (n / curW))
            {
                H = curH;
                W = curW;
            }
        }

        if (HERO != 1 && bestSucc > (n / H) * (n / W))
            continue;

        fprintf(stderr, "Chose %d x %d [%d blocks] for HERO %d\n", H, W, (n / H) * (n / W), HERO);

        int totalChunks = (n / H) * (n / W);
        int doneChunks = 0;

        int regNum = 1;
        Timing::resetClock();
        for (int i = 1; i <= n - H + 1; i += H)
        {
            for (int j = 1; j <= n - W + 1; j += W)
            {
                int success;
                if (TimeIsOK())
                {
                    if (HERO == 1)
                        success = solveRegion(i, j, i + H - 1, j + W - 1, C, false, true);
                    else
                    {
                        success = solveRegion(i, j, i + H - 1, j + W - 1, C);
                        if (success == 0 && C == 1)
                            success = solveRegion(i, j, i + H - 1, j + W - 1, C, true);
                    }
                }
                else
                    success = 0;
                //fprintf(stderr, "Calling %d, %d\n", i, j);
                if (success == 0)
                {
                    //fprintf(stderr, "FAILURE\n");
                    succ += pathicFill(i, j, regNum, 1, i, j, i + H - 1, j + W - 1);
                }
                else
                {
                    succ += success;
                    //fprintf(stderr, "SUCCESS\n");
                    for (int in = 1; in <= H; in++)
                    {
                        for (int ja = 1; ja <= W; ja++)
                        {
                            if (activeRegion[in][ja])
                                result[i + in - 1][j + ja - 1] = regNum;
                            else
                                result[i + in - 1][j + ja - 1] = regNum + color[in][ja];

                            //fprintf(stderr, "%d", (int)activeRegion[in][ja]);
                        }
                        //fprintf(stderr, "\n");
                    }
                    //fprintf(stderr, "\n");
                }

                doneChunks++;
                double interpolated = (double)succ / (double)doneChunks * (double)totalChunks;

                regNum += C + 1;
            }
        }
        Timing::showClock();

        int lastH = (n / H) * H;
        int lastW = (n / W) * W;

        if (lastW == n)
        {
            if (lastH != n)
                pathicFill(lastH + 1, 1, regNum, 1, 1, 1, n, n);
        }
        else
        {
            if (lastH % 2 == 0)
                pathicFill(1, n, regNum, -1, 1, 1, n, n);
            else
                pathicFill(1, lastW + 1, regNum, 1, 1, 1, n, n);
        }

        fprintf(stderr, "%d colors gives %d succ\n", C, succ);

        if (bestSucc == 0 || succ > bestSucc)
        {
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    remResult[i][j] = result[i][j];
                }
            }
            bestSucc = succ;
        }
        else
            break;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            result[i][j] = remResult[i][j];
        }
    }

    Verification::verify(result);

    ///

    int r = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (field[i][j] == HERO)
                r++;

            printf("%d", result[i][j]);
            if (j != n)
                printf(" ");
        }
        printf("\n");
    }

    fprintf(stderr, "Hero score (%d succs): %.2f\n", bestSucc, (double)(n * n) / (double)r * bestSucc);

    return (double)(n * n) / (double)r * bestSucc;
}


int main()
{
    freopen("gerrymandering.in", "r", stdin);
    freopen("gerrymandering.out", "w", stdout);

    scanf("%d %d %d", &n, &d, &p);
    R = n * n / d;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &field[i][j]);
            cnt[ field[i][j] ]++;
        }
    }

    double score = 0.0;
    for (int i = 1; i <= p; i++)
    {
        fprintf(stderr, "Count for %d is %d\n", i, cnt[i]);
        score += solveCase(i);
        fprintf(stderr, "\n");
    }

    fprintf(stderr, "Total score: %.2f\n", score);

    return 0;
}