#include <iostream>
#include <stdio.h>
#include <random>
#include <assert.h>
#include <time.h>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;
typedef long long llong;

bool LOCAL_RUN = false;

const double TIME_LIMIT = 3.0;
const double EPS = 1e-1;
bool TimeIsOK(double limit = TIME_LIMIT)
{
    return (double)clock() / (double)CLOCKS_PER_SEC < limit;
}

inline double fabs(double a)
{
    if (a < 0.0)
        return -a;
    else
        return a;
}

inline bool eq(double a, double b)
{
    return fabs(a - b) < EPS;
}

inline int sq(int a)
{
    return a * a;
}

inline double sq(double a)
{
    return a * a;
}

const llong SEED = 1337LL;
mt19937 mtn(SEED);
inline int mt()
{
    int v = abs(mtn());
    if (v < 0)
        return abs(v+1);
    else
        return v;
}
void resetRandom()
{
    mt19937 z(SEED);
    mtn = z;
}
llong bigr()
{
    return (llong)mt() * (llong)mt() + (llong)mt();
}

struct dcol
{
    double r, g, b;

    dcol(): r(0), g(0), b(0) {}
    dcol(double a, double b, double c): r(a), g(b), b(c) {}

    dcol operator+(const dcol &other) const
    {
        return dcol(r + other.r, g + other.g, b + other.b);
    }

    dcol operator/(const double v) const
    {
        return dcol(r / v, g / v, b / v);
    }

    dcol operator/(const int v) const
    {
        return (*this) / (double)v;
    }

    dcol operator*(const double v) const
    {
        return (*this) / (1.0 / v);
    }

    bool operator==(const dcol &other) const
    {
        return eq(r, other.r) && eq(g, other.g) && eq(b, other.b);
    }
};

struct col
{
    int r, g, b;

    col(): r(0), g(0), b(0) {}
    col(int a, int b, int c): r(a), g(b), b(c) {}

    static col fromDouble(dcol c)
    {
        return col(round(c.r), round(c.g), round(c.b));
    }

    static col randomCol()
    {
        return col(mt() % 256, mt() % 256, mt() % 256);
    }

    static col mix(col &a, col &b)
    {
        return fromDouble((a.toDouble() + b.toDouble()) / 2);
    }

    dcol toDouble()
    {
        return dcol(r, g, b);
    }

    bool operator<(const col &other) const
    {
        return make_pair(r, make_pair(g, b)) < make_pair(other.r, make_pair(other.g, other.b));
    }

    bool operator<=(const col &other) const
    {
        return make_pair(r, make_pair(g, b)) <= make_pair(other.r, make_pair(other.g, other.b));
    }

    bool operator==(const col &other) const
    {
        return r == other.r && g == other.g && b == other.b;
    }

    col operator+(const col &other) const
    {
        return col(r + other.r, g + other.g, b + other.b);
    }
};

int colDist(col &a, col &b)
{
    return sq(a.r - b.r) + sq(a.g - b.g) + sq(a.b - b.b);
}

double colDist(dcol &a, dcol &b)
{
    return sq(a.r - b.r) + sq(a.g - b.g) + sq(a.b - b.b);
}

template<class T>
vector< vector<T> > rot(vector< vector<T> > g)
{
    vector< vector<T> > res;
    int n = g.size(), m = g[0].size();
    int i,j;

    res.resize(m);
    for (i=0;i<res.size();i++)
    {
        for (j=n-1;j>=0;j--)
        {
            res[i].push_back(g[j][i]);
        }
    }

    return res;
}

struct compressorResult
{
    vector<col> palette;
    vector< vector<int> > rawColours;

    void print()
    {
        int i, j;

        for (i=0;i<palette.size();i++)
        {
            printf("%d %d %d\n", palette[i].r, palette[i].g, palette[i].b);
        }

        for (i=0;i<rawColours.size();i++)
        {
            for (j=0;j<rawColours[i].size();j++)
            {
                if (j != 0)
                    printf(" ");

                printf("%d",rawColours[i][j]);
            }
            printf("\n");
        }
    }
};

const int PS = 56;
int K = PS;
const int EXTRA = (PS - 16) * 5 + 1;
const int eM = (int)sqrt(EXTRA);
const int eN = (int)ceil((double)EXTRA / (double)eM);

class Compressor
{
    int n, m;
    col palette[PS];

    col tmpPalette[PS];
    dcol kmeans[PS];
    dcol nextGuess[PS];

    col initmeans[PS];

    double groupCount[PS];

    col pts[250111];
    double w[250111];
    int pL;

    int minDistances[250111];

    vector< vector<col> > img;

    void initKmeans()
    {
        int i, j, in;

        initmeans[0] = pts[mt() % pL];
        kmeans[0] = initmeans[0].toDouble();

        for (i=1;i<K;i++)
        {
            llong totalDist = 0;

            for (j=0;j<pL;j++)
            {
                int mind = colDist(pts[j], initmeans[0]);
                for (in=1;in<i;in++)
                {
                    mind = min(mind, colDist(pts[j], initmeans[in]));
                }

                minDistances[j] = mind;
                totalDist += (llong)mind;
            }

            if (totalDist == 0)
            {
                initmeans[i] = initmeans[i-1];
                kmeans[i] = initmeans[i].toDouble();
                continue;
            }

            llong sample = bigr() % totalDist;

            int choice = -1;
            for (j=0;j<pL;j++)
            {
                if (minDistances[j] > sample)
                {
                    choice = j;
                    break;
                }

                sample -= (llong)minDistances[j];
            }

            if (choice == -1)
            {
                initmeans[i] = initmeans[i-1];
            }
            else
            {
                initmeans[i] = pts[choice];
            }

            kmeans[i] = initmeans[i].toDouble();
        }
    }

    void kmeansPalette()
    {
        bool changes = true;
        int i, j;
        double bestCost = -1.0;

        while(TimeIsOK())
        {
            int iterations = 0;
            changes = true;

            initKmeans();

            double lastScore = -1.0;
            while(TimeIsOK() && changes)
            {
                iterations++;

                changes = false;

                for (i=0;i<K;i++)
                {
                    nextGuess[i].r = 0;
                    nextGuess[i].g = 0;
                    nextGuess[i].b = 0;
                    groupCount[i] = 0.0;
                }

                int choice;
                double dist;
                double score = 0.0;
                for (i=0;i<pL;i++)
                {
                    dist = 1e10;

                    for (j=0;j<K;j++)
                    {
                        double nDist = sq(pts[i].r - kmeans[j].r) + sq(pts[i].g - kmeans[j].g) + sq(pts[i].b - kmeans[j].b);

                        if (nDist < dist)
                        {
                            choice = j;
                            dist = nDist;
                        }
                    }

                    nextGuess[choice].r += pts[i].r * w[i];
                    nextGuess[choice].g += pts[i].g * w[i];
                    nextGuess[choice].b += pts[i].b * w[i];
                    groupCount[choice] += w[i];

                    score += dist * w[i];
                }

                for (i=0;i<K;i++)
                {
                    if (groupCount[i] > 0.0)
                        nextGuess[i] = nextGuess[i] / groupCount[i];

                    if (groupCount[i] > 0)
                    {
                        if (!eq(kmeans[i].r, nextGuess[i].r) || !eq(kmeans[i].g, nextGuess[i].g) || !eq(kmeans[i].b, nextGuess[i].b))
                            changes = true;

                        kmeans[i] = nextGuess[i];
                    }
                }

                if (iterations > 1)
                {
                    if ( fabs((score-lastScore)/lastScore*100.0) < 0.1 )
                        changes = false;
                }

                lastScore = score;
            }

            fprintf(stderr, "K-Means converged in %d iterations\n", iterations);

            for (i=0;i<K;i++)
            {
                tmpPalette[i] = col::fromDouble(kmeans[i]);
            }

            double curCost = 0;
            for (i=1;i<=pL;i++)
            {
                double cost = colDist(pts[i], tmpPalette[0]);
                for (j=1;j<K;j++)
                {
                    cost = min(cost, (double)colDist(pts[i], tmpPalette[j]));
                }
                curCost += cost * w[i];
            }

            fprintf(stderr, "Cur cost = %.1f\n", curCost);

            if (bestCost < 0 || curCost < bestCost)
            {
                bestCost = curCost;
                for (i=0;i<K;i++)
                {
                    palette[i] = tmpPalette[i];
                }
            }
        }
    }



    int rawColors[511][511];

    vector<int> to56(col c)
    {
        int num256 = c.r * 256 * 256 + c.g * 256 + c.b;
        vector<int> b56;
        int i;

        for (i=1;i<=5;i++)
        {
            b56.push_back(num256 % 56);
            num256 /= 56;
        }

        reverse(b56.begin(), b56.end());

        return b56;
    }

    void pasteColors(int x, int y, int code = 15)
    {
        int i, j, in, ja;

        assert( (x + y) % 2 == 0 );

        int curc = 16;
        vector<int> colorCode = to56(palette[curc]);
        int colorPart = 0;
        vector< pair<int,int> > tiles;

        for (i=x;i<x+2*eN;i+=2)
        {
            for (j=y;j<y+4*eM;j+=4)
            {
                if (curc >= K)
                    break;

                if (i == x && j == y)
                {
                    rawColors[i][j] = 7;
                    rawColors[i][j+1] = code;
                }
                else
                {
                    int v = colorCode[colorPart];
                    int v1 = v / 8, v2 = v % 8 + 8;

                    rawColors[i][j] = v1;
                    rawColors[i][j+1] = v2;

                    tiles.push_back(make_pair(v1, v2));

                    colorPart++;
                }

                if (colorPart == colorCode.size())
                {
                    colorPart = 0;
                    curc++;

                    if (curc < K)
                        colorCode = to56(palette[curc]);
                }
            }
        }

        assert(curc >= K);

        int tp = 0;
        for (i=x;i<x+2*eN;i+=2)
        {
            for (j=y;j<y+4*eM;j+=4)
            {
                if (tp >= tiles.size())
                    break;

                rawColors[i+1][j+1] = tiles[tp].first;
                rawColors[i+1][j+2] = tiles[tp].second;
                tp++;
            }
        }
    }

    compressorResult colorAugmentation(bool rotation, int kAdvice = -1)
    {
        if (kAdvice < 0)
            K = PS;
        else
            K = kAdvice;

        if (rotation)
        {
            img = rot(img);
            n = img.size();
            m = img[0].size();
        }

        int i, j, in, ja, i1, j1;
        int a, b, c;

        fprintf(stderr, "Color augmentation compression of picture size %d x %d [%d]\n", n, m, n*m);

        map<col, int> seenPt;
        map<col, int>::iterator it;

        pL = 0;
        for (i=0;i<n;i++)
        {
            for (j=i%2;j<m-1;j+=2)
            {
                col c = col::mix(img[i][j], img[i][j+1]);
                it = seenPt.find(c);
                if (it == seenPt.end())
                {
                    seenPt.insert(make_pair(c, pL));
                    pts[pL] = c;
                    w[pL] = 1.0;
                    pL++;
                }
                else
                {
                    w[(*it).second] += 1.0;
                }
            }
        }

        kmeansPalette();
        sort(palette, palette+K);

        if (rotation)
        {
            reorderPalette(2, 3);
        }

        int distScore = 0;
        for (i=0;i<n;i++)
        {
            int strt = 0;
            if (i % 2 == 1)
            {
                strt = 1;
                rawColors[i][0] = 8;
            }

            for (j=strt;j<m-1;j+=2)
            {
                col pairCol = col::mix(img[i][j], img[i][j+1]);

                int bestC = 0;
                int bestDif = colDist(img[i][j], palette[0]) + colDist(img[i][j+1], palette[0]);

                for (in=1;in<K;in++)
                {
                    int dst = colDist(img[i][j], palette[in]) + colDist(img[i][j+1], palette[in]);
                    if (dst < bestDif)
                    {
                        bestDif = dst;
                        bestC = in;
                    }
                }

                distScore += bestDif;

                rawColors[i][j] = bestC / 8;
                rawColors[i][j+1] = bestC % 8 + 8;
            }

            if ((i+m-1) % 2 == 1)
                rawColors[i][m-1] = 0;
        }

        int midx = n / 2, midy = m / 2;

        if ( (midx + midy) % 2 == 1 )
            midy++;

        pasteColors(midx + 1, midy + 1);
        pasteColors(midx + 1, midy - 1 - 4 * eM);
        pasteColors(midx - 1 - 2 * eN, midy - 1 - 4 * eM);
        pasteColors(midx - 1 - 2 * eN, midy + 1);

        fprintf(stderr, "Total distance %d\n", distScore);

        compressorResult res;

        for (i=0;i<K;i++)
        {
            res.palette.push_back(palette[i]);
        }
        res.palette.resize(16);

        for (i=0;i<n;i++)
        {
            vector<int> row;
            for (j=0;j<m;j++)
            {
                row.push_back(rawColors[i][j]);
            }
            res.rawColours.push_back(row);
        }

        if (rotation)
        {
            res.rawColours = rot(res.rawColours);
            res.rawColours = rot(res.rawColours);
            res.rawColours = rot(res.rawColours);
        }

        return res;
    }

    inline void reorderPalette(int A, int B)
    {
        assert(A < B);
        swap(palette[A], palette[B]);
        if (palette[A] == palette[B])
        {
            if (palette[A].r != 255)
                palette[A].r++;
            else
                palette[B].r--;
        }
    }

    compressorResult easyColor()
    {
        K = 16;

        int i, j, in, ja, i1, j1;
        int a, b, c;

        n = img.size();
        m = img[0].size();

        fprintf(stderr, "Easy compression of picture size %d x %d [%d]\n", n, m, n*m);

        map<col, int> seenPt;
        map<col, int>::iterator it;

        pL = 0;
        for (i=0;i<n;i++)
        {
            for (j=0;j<m;j++)
            {
                it = seenPt.find(img[i][j]);
                if (it == seenPt.end())
                {
                    seenPt.insert(make_pair(img[i][j], pL));
                    pts[pL] = img[i][j];
                    w[pL] = 1.0;
                    pL++;
                }
                else
                {
                    w[(*it).second] += 1.0;
                }
            }
        }

        kmeansPalette();
        sort(palette, palette+K);
        reorderPalette(0, 1);

        int distScore = 0;
        for (i=0;i<n;i++)
        {
            for (j=0;j<m;j++)
            {
                int bestC = 0;
                int bestDif = colDist(img[i][j], palette[0]);

                for (in=1;in<16;in++)
                {
                    int dst = colDist(img[i][j], palette[in]);
                    if (dst < bestDif)
                    {
                        bestDif = dst;
                        bestC = in;
                    }
                }

                distScore += bestDif;

                rawColors[i][j] = bestC;
            }
        }

        fprintf(stderr, "Total distance %d\n", distScore);

        compressorResult res;

        for (i=0;i<16;i++)
        {
            res.palette.push_back(palette[i]);
        }

        for (i=0;i<n;i++)
        {
            vector<int> row;
            for (j=0;j<m;j++)
            {
                row.push_back(rawColors[i][j]);
            }
            res.rawColours.push_back(row);
        }

        return res;
    }

    bool augFits(int N, int M)
    {
        return M >= 4 * eM * 2 + 4 && N >= 2 * eN * 2 + 4;
    }

    const int TOLERANCE = 2000;
    pair<int,llong> easyEstimate()
    {
        int i,j,in;
        vector<col> basis;
        llong easyEstimate = 0;

        for (i=0;i<n;i++)
        {
            for (j=0;j<m;j++)
            {
                if (basis.empty())
                {
                    basis.push_back(img[i][j]);
                }
                else
                {
                    int minDist = colDist(img[i][j], basis[0]);

                    for (in=1;in<basis.size();in++)
                    {
                        minDist = min(minDist, colDist(img[i][j], basis[in]));
                    }

                    if (minDist > TOLERANCE)
                    {
                        basis.push_back(img[i][j]);
                    }
                    else
                        easyEstimate += (llong)minDist;
                }
            }
        }

        fprintf(stderr,"Easy estimate: %lld\n", easyEstimate);

        return make_pair((int)basis.size(), easyEstimate);
    }

    int blendCost(col A, col B)
    {
        col mix = col::mix(A, B);
        return colDist(A, mix) + colDist(B, mix);
    }

    pair<llong,llong> augEstimates()
    {
        int i,j;
        llong estH = 0;

        for (i=0;i<n;i++)
        {
            for (j=i%2;j<m-1;j+=2)
            {
                col mid = col::mix(img[i][j], img[i][j+1]);
                estH += colDist(img[i][j], mid) + colDist(img[i][j+1], mid);
            }

            if (i % 2 == 1)
                estH += colDist(img[i][0], img[i][1]);
            if ((m-1)%2 == 0)
                estH += colDist(img[i][m-1], img[i][m-2]);
        }

        fprintf(stderr, "Horizontal estimate %lld\n", estH);

        llong estV = 0;

        for (i=0;i<m;i++)
        {
            for (j=i%2;j<n-1;j+=2)
            {
                col mid = col::mix(img[j][i], img[j+1][i]);
                estV += colDist(img[j][i], mid) + colDist(img[j+1][i], mid);
            }

            if (i % 2 == 1)
                estV += colDist(img[0][i], img[1][i]);
            if ((n-1)%2 == 0)
                estV += colDist(img[n-1][i], img[n-2][i]);
        }

        fprintf(stderr, "Vertical estimate %lld\n", estV);

        llong mixedEst = 0;
        for (i=0;i<n-1;i+=2)
        {
            for (j=0;j<m-1;j+=2)
            {
                vector<col> cs;
                cs.push_back(img[i][j]);
                cs.push_back(img[i+1][j]);
                cs.push_back(img[i][j+1]);
                cs.push_back(img[i+1][j+1]);

                int cost  = blendCost(cs[0], cs[1]) + blendCost(cs[2], cs[3]);
                cost = min(cost, blendCost(cs[0], cs[2]) + blendCost(cs[1], cs[3]));
                cost = min(cost, blendCost(cs[0], cs[3]) + blendCost(cs[1], cs[2]));

                mixedEst += cost;
            }

            if (m % 2 == 1)
                mixedEst += colDist(img[i][m-1], img[i][m-2]);
        }

        if (n % 2 == 1)
        {
            for (i=0;i<m;i++)
            {
                mixedEst += colDist(img[n-1][i], img[n-2][i]);
            }
        }

        fprintf(stderr, "Mixed cost %d\n", mixedEst);

        return make_pair(estH, estV);
    }

    public:

    compressorResult compress(vector< vector<col> > &rimg)
    {
        img = rimg;

        n = img.size();
        m = img[0].size();

        pair<int,llong> easyEst = easyEstimate();
        int colorFactor = easyEst.first;
        pair<llong,llong> augEst = augEstimates();

        if (!augFits(n, m))
            augEst.first = 1000000000LL;
        if (!augFits(m, n))
            augEst.second = 1000000000LL;

        fprintf(stderr, "Color factor: %d\n", colorFactor);

        double goalFrac = 1.0;
        if (colorFactor <= 10)
        {
            goalFrac = 100.0;
        }
        else if (colorFactor < 33)
        {
            goalFrac = 1.0 + 2 * ((33.0 - colorFactor) / 22.0);
        }

        if (n < 100 || m < 100 || n * m < 30000)
        {
            return easyColor();
        }
        else
        {
            double frac = (double)easyEst.second / (double)min(augEst.first, augEst.second);

            if (frac < goalFrac)
                return easyColor();
            else
            {
                if (augEst.first <= augEst.second)
                    return colorAugmentation(false);
                else
                    return colorAugmentation(true);
            }
        }
    }
};

struct decompressorResult
{
    vector< vector<col> > img;

    void print()
    {
        int i, j;

        for (i=0;i<img.size();i++)
        {
            for (j=0;j<img[i].size();j++)
            {
                if (j != 0)
                    printf(" ");
                printf("%d %d %d",img[i][j].r,img[i][j].g,img[i][j].b);
            }
            printf("\n");
        }
    }
};

class Decompressor
{
    int n, m;
    vector<col> palette;

    vector< vector<col> > img;
    vector< vector<int> > raw;

    col tmp[511][511];

    bool displaced[511][511];

    int dispNbs[511][511];
    vector< pair<int,int> > nbs[511][511];

    vector< pair<int,int> > component;
    bool TFO[511][511];
    void getComponent(int x, int y)
    {
        if (x < 0 || y < 0 || x >= n || y >= m)
            return;
        if (TFO[x][y] || !displaced[x][y])
            return;
        TFO[x][y] = true;
        component.push_back(make_pair(x, y));

        getComponent(x+1, y);
        getComponent(x-1, y);
        getComponent(x, y+1);
        getComponent(x, y-1);
    }

    vector<int> cmpSizes;
    int matched[250111];

    int usualMatch[250111];
    int usualValue[250111];

    void batrak(int ind)
    {
        int i;

        if (ind == component.size())
        {
            for (i=0;i<component.size();i++)
            {
                if (usualMatch[i] == -2)
                    usualMatch[i] = matched[i];
                else if (usualMatch[i] != matched[i])
                    usualMatch[i] = -1;

                if (usualValue[i] == -2)
                    usualValue[i] = raw[ component[ matched[i] ].first ][ component[ matched[i] ].second ];
                else if (usualValue[i] != raw[ component[ matched[i] ].first ][ component[ matched[i] ].second ])
                    usualValue[i] = -1;
            }

            return;
        }

        if (matched[ind] != -1)
        {
            batrak(ind+1);
            return;
        }

        for (i=ind+1;i<component.size();i++)
        {
            if ( matched[i] == -1 && abs(component[ind].first - component[i].first) + abs(component[ind].second - component[i].second) == 1 )
            {
                matched[i] = ind;
                matched[ind] = i;
                batrak(ind+1);
                matched[i] = -1;
                matched[ind] = -1;
            }
        }
    }

    void solveComponent()
    {
        cmpSizes.push_back(component.size());

        int i;

        for (i=0;i<component.size();i++)
        {
            matched[i] = -1;
            usualValue[i] = -2;
            usualMatch[i] = -2;
        }
        batrak(0);

        bool allFixed = true;
        for (i=0;i<component.size();i++)
        {
            if (usualValue[i] < 0)
                allFixed = false;
        }

        if (allFixed)
        {
            for (i=0;i<component.size();i++)
            {
                pair<int,int> v = component[i];
                displaced[v.first][v.second] = false;
                raw[v.first][v.second] = usualValue[i];
            }
        }

        component.clear();
    }

    void buildCertainMatches()
    {
        int i,j;

        memset(TFO,false,sizeof(TFO));

        for (i=0;i<n;i++)
        {
            for (j=0;j<m;j++)
            {
                if (displaced[i][j] && !TFO[i][j])
                {
                    getComponent(i, j);
                    solveComponent();
                }
            }
        }

        sort(cmpSizes.begin(), cmpSizes.end());
        reverse(cmpSizes.begin(), cmpSizes.end());

        for (i=0;i<min((int)cmpSizes.size(), 20);i++)
        {
            fprintf(stderr, "%d ",cmpSizes[i]);
        }
        fprintf(stderr, "\n");
    }

    bool BREAK = false;

    vector< pair<int,int> > toMatch;
    bool negated = false;

    bool isStart(int x, int y)
    {
        return ((x + y) % 2 == 0) != negated;
    }

    void fixShuffle()
    {
        int i, j, in, ja;
        int disbalance = 0;

        for (i=0;i<n;i++)
        {
            for (j=0;j<m;j++)
            {
                if ( (i+j) % 2 == 0 )
                {
                    if (raw[i][j] < 8)
                        disbalance++;
                    else
                        disbalance--;
                }
            }
        }

        if (disbalance < 0)
            negated = true;

        for (i=0;i<n;i++)
        {
            for (j=0;j<m;j++)
            {
                if ( (i+j) % 2 == 0 )
                {
                    if (raw[i][j] < 8)
                        displaced[i][j] = negated;
                    else
                        displaced[i][j] = !negated;
                }
                else
                {
                    if (raw[i][j] < 8)
                        displaced[i][j] = !negated;
                    else
                        displaced[i][j] = negated;
                }
            }
        }

        int displacedCtr = 0;
        for (i=0;i<n;i++)
        {
            for (j=0;j<m;j++)
            {
                if (!displaced[i][j])
                    continue;

                displacedCtr++;

                for (in=-1;in<=1;in++)
                {
                    for (ja=-1;ja<=1;ja++)
                    {
                        if (abs(in) + abs(ja) != 1)
                            continue;
                        int x = i + in, y = j + ja;
                        if (x < 0 || y < 0 || x >= n || y >= m)
                            continue;
                        if (displaced[x][y])
                        {
                            dispNbs[i][j]++;
                            nbs[i][j].push_back(make_pair(x, y));
                        }
                    }
                }

                if (dispNbs[i][j] == 1)
                    toMatch.push_back(make_pair(i, j));

                assert(dispNbs[i][j] > 0);
            }
        }

        fprintf(stderr, "%d colors displaced\n", displacedCtr);

        while(!toMatch.empty())
        {
            int x = toMatch.back().first, y = toMatch.back().second;
            toMatch.pop_back();

            if (!displaced[x][y])
                continue;

            int xm = -1, ym = -1;
            for (i=0;i<nbs[x][y].size();i++)
            {
                if (displaced[ nbs[x][y][i].first ][ nbs[x][y][i].second ])
                {
                    xm = nbs[x][y][i].first;
                    ym = nbs[x][y][i].second;
                    break;
                }
            }
            assert(xm != -1);

            swap(raw[x][y], raw[xm][ym]);
            displaced[x][y] = false;
            displaced[xm][ym] = false;

            for (i=0;i<nbs[xm][ym].size();i++)
            {
                int xn = nbs[xm][ym][i].first, yn = nbs[xm][ym][i].second;
                dispNbs[xn][yn]--;
                if (dispNbs[xn][yn] == 1)
                {
                    toMatch.push_back(make_pair(xn, yn));
                }
            }
        }

        displacedCtr = 0;
        for (i=1;i<=n;i++)
        {
            for (j=1;j<=m;j++)
            {
                if (displaced[i][j])
                {
                    displacedCtr++;
                }
            }
        }

        fprintf(stderr, "%d colors displaced after fix\n", displacedCtr);

        buildCertainMatches();

        displacedCtr = 0;
        for (i=1;i<=n;i++)
        {
            for (j=1;j<=m;j++)
            {
                if (displaced[i][j])
                {
                    displacedCtr++;
                }
            }
        }

        fprintf(stderr, "%d colors displaced after certain matching\n", displacedCtr);
    }

    col from256toCol(int num)
    {
        return col(num / (256 * 256), (num / 256) % 256, num % 256);
    }

    inline bool inside(int x, int y)
    {
        return x >= 0 && y >= 0 && x < n && y < m;
    }

    vector< vector<int> > paletteParts;
    vector< pair<int,int> > colorInfo;

    int allowedOutside;

    int failures = 0;
    void processBarcode(int x, int y, bool forceInside = false)
    {
        int i, j;

        if (x >= 1 && y >= 1 && x < n - 1 && y < m - 1)
        {
            bool good = false;
            for (i=-1;i<=1;i++)
            {
                for (j=-1;j<=1;j++)
                {
                    if (raw[x+i][y+j] == 7)
                        good = true;
                }
            }

            if (!good)
                return;
        }
        else if (allowedOutside == 0 || forceInside)
            return;

        for (i=0;i<colorInfo.size();i++)
        {
            if (colorInfo[i] == make_pair(x, y))
                return;
        }

        allowedOutside--;

        colorInfo.push_back(make_pair(x, y));
        fprintf(stderr,"Detected code at %d, %d\n", x, y);

        int curc = 16;
        int parts = 0;

        if (x >= 0 && x < n && y >= 0 && y < n)
            displaced[x][y] = true;

        if (x >= 0 && x < n && y+1 >= 0 && y+1 < n)
            displaced[x][y+1] = true;

        for (i=x;i<x+2*eN;i+=2)
        {
            for (j=y;j<y+4*eM;j+=4)
            {
                if (inside(i+1, j+1))
                    displaced[i+1][j+1] = true;
                if (inside(i+1, j+2))
                    displaced[i+1][j+2] = true;

                if (i == x && j == y)
                    continue;
                if (curc >= K)
                    break;

                if (inside(i, j) && inside(i, j+1))
                {
                    int v = raw[i][j] * 8 + raw[i][j+1] - 8;

                    if (!displaced[i][j] && !displaced[i][j+1])
                    {
                        paletteParts[curc][parts] = v;
                    }
                }

                if (inside(i, j))
                    displaced[i][j] = true;
                if (inside(i, j+1))
                    displaced[i][j+1] = true;

                parts++;
                if (parts == 5)
                {
                    parts = 0;
                    curc++;
                }
            }
        }

        curc = 16;
        parts = 0;

        for (i=x;i<x+2*eN;i+=2)
        {
            for (j=y;j<y+4*eM;j+=4)
            {
                if (curc >= K)
                    break;

                if (inside(i+1, j+1) && inside(i+1, j+2))
                {
                    int v = raw[i+1][j+1] * 8 + raw[i+1][j+2] - 8;

                    if (!displaced[i+1][j+1] && !displaced[i+1][j+2])
                    {
                        paletteParts[curc][parts] = v;
                    }
                }

                if (inside(i+1, j+1))
                    displaced[i+1][j+1] = true;
                if (inside(i+1, j+2))
                    displaced[i+1][j+2] = true;

                parts++;
                if (parts == 5)
                {
                    parts = 0;
                    curc++;
                }
            }
        }
    }

    void generateOthers(pair<int,int> A, pair<int,int> B)
    {
        if (A.first != B.first && A.second != B.second) /// 1, 4
        {
            processBarcode(A.first, B.second, true);
            processBarcode(B.first, A.second, true);

            processBarcode(A.first, B.second);
            processBarcode(B.first, A.second);
        }
        else if (A.first == B.first) ///2, 6
        {
            processBarcode(A.first + 2*eN + 2, A.second, true);
            processBarcode(B.first + 2*eN + 2, B.second, true);
            processBarcode(A.first - 2*eN - 2, A.second, true);
            processBarcode(B.first - 2*eN - 2, B.second, true);

            processBarcode(A.first + 2*eN + 2, A.second);
            processBarcode(B.first + 2*eN + 2, B.second);
            processBarcode(A.first - 2*eN - 2, A.second);
            processBarcode(B.first - 2*eN - 2, B.second);
        }
        else ///3, 5
        {
            processBarcode(A.first, A.second + 4*eM + 2, true);
            processBarcode(B.first, B.second + 4*eM + 2, true);
            processBarcode(A.first, A.second - 4*eM - 2, true);
            processBarcode(B.first, B.second - 4*eM - 2, true);

            processBarcode(A.first, A.second + 4*eM + 2);
            processBarcode(B.first, B.second + 4*eM + 2);
            processBarcode(A.first, A.second - 4*eM - 2);
            processBarcode(B.first, B.second - 4*eM - 2);
        }
    }

    void generateFromSingle(pair<int,int> A)
    {
        processBarcode(A.first - 2*eN - 2, A.second, true);
        processBarcode(A.first + 2*eN + 2, A.second, true);
        processBarcode(A.first, A.second - 4*eM - 2, true);
        processBarcode(A.first, A.second + 4*eM + 2, true);
    }

    void learnColors()
    {
        int i, j, in, ja;

        paletteParts.resize(palette.size());
        for (i=0;i<paletteParts.size();i++)
        {
            paletteParts[i].resize(5);
            for (j=0;j<5;j++)
            {
                paletteParts[i][j] = -1;
            }
        }

        int sevens = 0;

        allowedOutside = 4;
        for (i=0;i<n;i++)
        {
            for (j=0;j<m-1;j++)
            {
                if (raw[i][j] == 7 && raw[i][j+1] == 15 && !displaced[i][j] && !displaced[i][j+1])
                {
                    processBarcode(i, j);
                }
                else if (raw[i][j] == 7)
                {
                    fprintf(stderr, "Detected bad code at %d, %d\n", i, j);
                }

                if (raw[i][j] == 7)
                    sevens++;
            }
        }

        if (colorInfo.size() == 1)
        {
            generateFromSingle(colorInfo[0]);
        }

        if (colorInfo.size() >= 2)
        {
            generateOthers(colorInfo[0], colorInfo[1]);
        }

        for (i=16;i<paletteParts.size();i++)
        {
            bool learned = true;
            int colorNum = 0;
            for (j=0;j<5;j++)
            {
                if (paletteParts[i][j] == -1)
                {
                    learned = false;
                    break;
                }

                colorNum *= 56;
                colorNum += paletteParts[i][j];
            }

            if (learned)
            {
                palette[i] = from256toCol(colorNum);
                fprintf(stderr, "Learned color %d\n", i);
            }
            else
            {
                fprintf(stderr, "WARNING: Color %d severely corrupted\n", i);
                palette[i] = col(-1, -1, -1);
            }
        }
    }

    pair<int,int> q[250111];
    int qL = 0;

    bool inq[511][511];
    int imgColCtr[511][511];

    void fillDisplacements()
    {
        int uk = 0;
        int i, j;

        for (i=0;i<n;i++)
        {
            for (j=0;j<m;j++)
            {
                if (!displaced[i][j])
                {
                    inq[i][j] = true;
                    q[qL] = make_pair(i, j);
                    imgColCtr[i][j] = 1;
                    qL++;
                }
                else
                {
                    inq[i][j] = false;
                    img[i][j] = col(0, 0, 0);
                    imgColCtr[i][j] = 0;
                }
            }
        }

        while(uk < qL)
        {
            int x = q[uk].first, y = q[uk].second;

            displaced[x][y] = false;
            assert(imgColCtr[x][y] > 0);
            img[x][y] = col::fromDouble(img[x][y].toDouble() / imgColCtr[x][y]);

            for (i=-1;i<=1;i++)
            {
                for (j=-1;j<=1;j++)
                {
                    if (abs(i) + abs(j) != 1)
                        continue;
                    int nx = x + i, ny = y + j;
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                        continue;
                    if (!displaced[nx][ny])
                        continue;

                    if (!inq[nx][ny])
                    {
                        q[qL] = make_pair(nx, ny);
                        qL++;
                        inq[nx][ny] = true;
                    }

                    img[nx][ny] = img[nx][ny] + img[x][y];
                    imgColCtr[nx][ny]++;
                }
            }

            uk++;
        }
    }

    int rawImageView[511][511];

    decompressorResult colorAugmentation()
    {
        int i, j, in, ja;

        bool rotation = (palette[3] < palette[2]);

        if (rotation)
        {
            fprintf(stderr, "ROTATION!\n");
            raw = rot(raw);
        }

        n = raw.size();
        m = raw[0].size();

        palette.resize(PS);

        fprintf(stderr,"Color Augmentation decompressing %d x %d [%d]\n", n, m, n*m);

        fixShuffle();
        learnColors();

        fprintf(stderr,"Shuffle fixed\n");

        img.resize(n);
        for (i=0;i<n;i++)
        {
            img[i].resize(m);
            for (j=0;j<m;j++)
            {
                img[i][j] = palette[ raw[i][j] ];
            }
        }

        for (i=0;i<n;i++)
        {
            j = 0;
            while(j < m)
            {
                if (isStart(i, j) && j + 1 < m)
                {
                    if (displaced[i][j] || displaced[i][j+1])
                    {
                        displaced[i][j] = true;
                        displaced[i][j+1] = true;

                        rawImageView[i][j] = -1;
                        rawImageView[i][j+1] = -1;

                        j += 2;
                        continue;
                    }

                    int colorInd = raw[i][j] * 8 + raw[i][j+1] - 8;

                    if (colorInd < PS)
                    {
                        if (palette[colorInd].r < 0)
                        {
                            displaced[i][j] = true;
                            displaced[i][j+1] = true;
                            rawImageView[i][j] = -1;
                            rawImageView[i][j+1] = -1;
                        }
                        else
                        {
                            img[i][j] = palette[colorInd];
                            img[i][j+1] = img[i][j];

                            rawImageView[i][j] = colorInd;
                            rawImageView[i][j+1] = colorInd;
                        }
                    }
                    else
                    {
                        img[i][j] = col(255, 255, 255);
                        img[i][j+1] = col(255, 255, 255);

                        displaced[i][j] = true;
                        displaced[i][j+1] = true;

                        rawImageView[i][j] = -1;
                        rawImageView[i][j+1] = -1;
                    }

                    j += 2;
                }
                else
                    j++;
            }

            if (!isStart(i, 0))
            {
                displaced[i][0] = true;
                rawImageView[i][0] = -1;
            }
            if (isStart(i, m-1))
            {
                displaced[i][m-1] = true;
                rawImageView[i][m-1] = -1;
            }
        }

        fillDisplacements();

        decompressorResult res;

        if (true)
        {
            for (i=0;i<n;i++)
            {
                vector<col> row;
                for (j=0;j<m;j++)
                {
                    col mnc = col(0, 0, 0);
                    int ctr = 0;
                    int diffs = 0;

                    bool unusable = rawImageView[i][j] == -1;

                    for (in=-1;in<=1;in++)
                    {
                        for (ja=-1;ja<=1;ja++)
                        {
                            if (abs(in) + abs(ja) != 1)
                                continue;

                            int x = i + in, y = j + ja;

                            if (x < 0 || y < 0 || x >= n || y >= m)
                                continue;

                            if (rawImageView[x][y] != rawImageView[i][j])
                                diffs++;

                            ctr++;
                            mnc = mnc + img[x][y];
                        }
                    }

                    mnc = col::fromDouble(mnc.toDouble() / ctr);

                    if (diffs >= 2 && !unusable)
                    {
                        double selfWeight = 0.5;
                        dcol c = (mnc.toDouble() * (1.0 - selfWeight)) + (img[i][j].toDouble() * selfWeight);

                        row.push_back(col::fromDouble(c));
                    }
                    else
                        row.push_back(img[i][j]);
                }
                res.img.push_back(row);
            }
        }
        else
        {
            for (i=0;i<n;i++)
            {
                vector<col> row;
                for (j=0;j<m;j++)
                {
                    if (BREAK)
                    {
                        row.push_back(col(0, 0, 0));
                        continue;
                    }
                    row.push_back(img[i][j]);
                }
                res.img.push_back(row);
            }
        }

        if (rotation)
        {
            res.img = rot(res.img);
            res.img = rot(res.img);
            res.img = rot(res.img);
        }

        return res;
    }

    decompressorResult easyColor()
    {
        int i, j, in, ja;

        n = raw.size();
        m = raw[0].size();

        fprintf(stderr,"Easy color decompressing %d x %d [%d]\n", n, m, n*m);

        for (i=0;i<n;i++)
        {
            vector<col> row;
            for (j=0;j<m;j++)
            {
                row.push_back(palette[ raw[i][j] ]);
            }
            img.push_back(row);
        }

        decompressorResult res;

        for (i=0;i<n;i++)
        {
            vector<col> row;
            for (j=0;j<m;j++)
            {
                col mnc = col(0, 0, 0);
                int ctr = 0;
                int diffs = 0;

                for (in=-1;in<=1;in++)
                {
                    for (ja=-1;ja<=1;ja++)
                    {
                        if (abs(in) + abs(ja) != 1)
                            continue;

                        int x = i + in, y = j + ja;

                        if (x < 0 || y < 0 || x >= n || y >= m)
                            continue;

                        if (raw[x][y] != raw[i][j])
                            diffs++;

                        ctr++;
                        mnc = mnc + img[x][y];
                    }
                }

                mnc = col::fromDouble(mnc.toDouble() / ctr);

                if (diffs >= 2)
                {
                    double selfWeight = 0.5;
                    dcol c = (mnc.toDouble() * (1.0 - selfWeight)) + (img[i][j].toDouble() * selfWeight);

                    row.push_back(col::fromDouble(c));
                }
                else
                    row.push_back(img[i][j]);
            }
            res.img.push_back(row);
        }

        return res;
    }

    public:

    decompressorResult decompress(vector<col> &rawpalette, vector< vector<int> > &rawinp)
    {
        raw = rawinp;
        palette = rawpalette;

        if (palette[0] <= palette[1])
        {
            return colorAugmentation();
        }
        else
        {
            return easyColor();
        }
    }
};

vector< vector<col> > readRun0()
{
    vector< vector<col> > res;
    int n,m;
    int i,j;

    scanf("%d %d",&m,&n);

    for (i=0;i<n;i++)
    {
        vector<col> row;
        for (j=0;j<m;j++)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            row.push_back(col(a,b,c));
        }
        res.push_back(row);
    }

    return res;
}

vector<col> readPalette()
{
    int i;
    vector<col> palette;

    for (i=0;i<16;i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        palette.push_back(col(a,b,c));
    }

    return palette;
}

vector< vector<int> > readRawImg()
{
    int i, j;
    int n, m;
    vector< vector<int> > res;

    scanf("%d %d",&m,&n);

    for (i=0;i<n;i++)
    {
        vector<int> row;

        for (j=0;j<m;j++)
        {
            int r;
            scanf("%d",&r);
            row.push_back(r);
        }
        res.push_back(row);
    }

    return res;
}

pair< pair<int,int>, pair<int,int> > getWindow(int n, int m)
{
    int vertLimit = n / 5;
    int horizLimit = m / 5;

    return make_pair( make_pair(mt() % vertLimit, mt() % horizLimit), make_pair(n - 1 - mt() % vertLimit, m - 1 - mt() % horizLimit) );
}

bool swapped[511][511];
vector< vector<int> > cutShuffle(vector< vector<int> > &raw, pair< pair<int,int>, pair<int,int> > window)
{
    memset(swapped, false, sizeof(swapped));

    vector< vector<int> > res;
    int i, j;

    for (i=window.first.first;i<=window.second.first;i++)
    {
        vector<int> row;
        for (j=window.first.second;j<=window.second.second;j++)
        {
            row.push_back(raw[i][j]);
        }
        res.push_back(row);
    }

    int n = res.size(), m = res[0].size();
    int swaps = (n * m) / 10;

    while(swaps > 0)
    {
        int x = mt() % n, y = mt() % m;
        int bx = x, by = y;

        int g = mt() % 4;
        if (g == 0)
            x++;
        else if (g == 1)
            x--;
        else if (g == 2)
            y++;
        else
            y--;

        if (x < 0 || y < 0 || x >= n || y >= m)
            continue;
        if (swapped[x][y] || swapped[bx][by])
            continue;

        swap(res[x][y], res[bx][by]);
        swapped[x][y] = true;
        swapped[bx][by] = true;

        swaps--;
    }

    return res;
}

void analyze(vector< vector<col> > &img, compressorResult &cRes, decompressorResult &dRes, pair< pair<int,int>, pair<int,int> > window)
{
    int i,j;

    fprintf(stderr,"-----ANALYZE-----\n");
    fprintf(stderr, "Cut to %d, %d to %d, %d\n", window.first.first, window.first.second, window.second.first, window.second.second);

    int score = 0;
    for (i=0;i<dRes.img.size();i++)
    {
        for (j=0;j<dRes.img[i].size();j++)
        {
            score += colDist(dRes.img[i][j], img[i+window.first.first][j+window.first.second]);
        }
    }

    int idealScore = 0;
    for (i=window.first.first;i<window.second.first;i++)
    {
        for (j=window.first.second;j<window.second.second;j++)
        {
            idealScore += colDist(cRes.palette[ cRes.rawColours[i][j] ], img[i][j]);
        }
    }

    fprintf(stderr, "Score: %d\n", score);
    fprintf(stderr, "Ideal: %d\n", idealScore);
}

int main()
{
    if (LOCAL_RUN)
    {
        freopen("03.in","r",stdin);
        freopen("imrec.out","w",stdout);
    }
    else
    {
        freopen("imrec.in","r",stdin);
        freopen("imrec.out","w",stdout);
    }

    int run;
    scanf("%d",&run);

    if (LOCAL_RUN)
    {
        vector< vector<col> > img = readRun0();

        Compressor C;
        compressorResult cRes = C.compress(img);

        resetRandom();

        pair< pair<int,int>, pair<int,int> > window = getWindow(cRes.rawColours.size(), cRes.rawColours[0].size());
        vector< vector<int> > noisy = cutShuffle(cRes.rawColours, window);

        Decompressor D;
        decompressorResult dRes = D.decompress(cRes.palette, noisy);

        analyze(img, cRes, dRes, window);
    }
    else
    {
        if (run == 0)
        {
            Compressor C;
            vector< vector<col> > img = readRun0();
            C.compress(img).print();
        }
        else
        {
            Decompressor D;
            vector<col> p = readPalette();
            vector< vector<int> > raw = readRawImg();
            D.decompress(p, raw).print();
        }
    }

    return 0;