#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;
typedef unsigned char byte;
struct rgb {
    union {
        byte c[3];
        struct { byte r, g, b; };
    };
    void set(byte r_, byte g_, byte b_)
    {
        r = r_;
        g = g_;
        b = b_;
    }
};
int W, H;
const int MAX_WH = 500;
const int MAX_SIZE = MAX_WH * MAX_WH;
rgb rgbImage[MAX_SIZE];
byte indexedImage[MAX_SIZE];
int indices[MAX_SIZE];
rgb palette[16];
int comps[16];
byte medians[16];

void saveBMP(const char* fname)
{
    struct bmpInfoHeader
    {
        unsigned int size;
        int w, h;
        unsigned short planes, bitcount;
        unsigned int compr, biSizeImage;
        int biXPelsPerMeter, biYPelsPerMeter;
        unsigned int biClrUsed, biClrImportant;

        bmpInfoHeader()
        {
            memset(this, 0, sizeof(bmpInfoHeader));
            size = sizeof(bmpInfoHeader);
            w = W;
            h = -H;
            planes = 1;
            bitcount = 32;
            compr = 0; // BI_RGB
        }
    } bih;

    struct bmpFileHeader
    {
        byte magic[2];
        byte size[4];
        byte res[4];
        byte off[4];

        bmpFileHeader()
        {
            magic[0] = 'B';
            magic[1] = 'M';
            memset(res, 0, sizeof(res));

            (*(int*)size) = sizeof(bmpFileHeader) + sizeof(bmpInfoHeader) + W * 4 * H;
            (*(int*)off) = sizeof(bmpFileHeader) + sizeof(bmpInfoHeader);
        }
    } bfh;
    ofstream fbmp(fname, ios::out | ios::binary);
    fbmp.write((const char*)&bfh, sizeof(bfh));
    fbmp.write((const char*)&bih, sizeof(bih));
    byte row[MAX_WH * 4];
    for (int y = 0, o = 0; y < H; y++)
    {
        for (int x = 0, r = 0; x < W; x++, o++)
        {
            row[r++] = rgbImage[o].b;
            row[r++] = rgbImage[o].g;
            row[r++] = rgbImage[o].r;
            row[r++] = 255;
        }
        fbmp.write((const char*)row, W * 4);
    }
}

void getRanges(int arr[], int cnt, rgb& min, rgb& max)
{
    min.set(255, 255, 255);
    max.set(0, 0, 0);
    for (int i = 0; i < cnt; i++)
    {
        auto& p = rgbImage[arr[i]];
        if (max.r < p.r) max.r = p.r;
        if (max.g < p.g) max.g = p.g;
        if (max.b < p.b) max.b = p.b;
        if (min.r > p.r) min.r = p.r;
        if (min.g > p.g) min.g = p.g;
        if (min.b > p.b) min.b = p.b;
    }
}

int getMaxRange(const rgb& min, const rgb& max)
{
    byte dr = max.r - min.r, dg = max.g - min.g, db = max.b - min.b;
    return dr > dg ? (dr > db ? 0 : 2) : (dg > db ? 1 : 2);
}

void sortRange(int arr[], int cnt, int clr)
{
    sort(arr, arr + cnt, [clr](int l, int r) -> bool { return (int)rgbImage[l].c[clr] < (int)rgbImage[r].c[clr]; });
}

void processRange(int arr[], int cnt, int pos)
{
    if (pos >= 16)
    {
        int tr = 0, tg = 0, tb = 0;
        for (int i = 0; i < cnt; i++)
        {
            auto& p = rgbImage[arr[i]];
            tr += p.r;
            tg += p.g;
            tb += p.b;
        }
        auto& ap = palette[pos - 16];
        ap.r = (byte)(tr / cnt);
        ap.g = (byte)(tg / cnt);
        ap.b = (byte)(tb / cnt);
        return;
    }
    rgb min, max;
    getRanges(arr, cnt, min, max);
    int comp = comps[pos] = getMaxRange(min, max);
    sortRange(arr, cnt, comp);

    int half = cnt / 2;
    medians[pos] = rgbImage[arr[half]].c[comp];
    processRange(arr, half, 2 * pos);
    processRange(arr + half, cnt - half, 2 * pos + 1);
}

void initPaletteMedianCut()
{
    int count = W * H;
    for (int i = 0; i < count; i++)
        indices[i] = i;

    processRange(indices, count, 1);
}

byte rgb2IndexMedianCut(const rgb& p)
{
    int pos = 1;
    int index = 0;
    for (int i = 0; i < 4; i++, index <<= 1)
    {
        if (p.c[comps[pos]] < medians[pos])
        {
            pos = 2 * pos;
        }
        else
        {
            pos = 2 * pos + 1;
            index++;
        }
    }
    return index >> 1;
}

int compress(ifstream& fin, ofstream& fout)
{
    fin >> W >> H;
    if (W <= 0 || W > MAX_WH || H <= 0 || H > MAX_WH)
    {
        cout << "invalid size (" << W << ", " << H << ")" << endl;
        return 2;
    }

    for (int y = 0, o = 0; y < H; y++)
    {
        for (int x = 0; x < W; x++, o++)
        {
            int r, g, b;
            fin >> r >> g >> b;
            if (r < 0 || r > 255 || g < 0 || g > 255 || b < 0 || b > 255)
            {
                cout << "invalid pixel: " << r << ", " << g << ", " << b << endl;
                return 3;
            }
            rgbImage[o].set((byte)r, (byte)g, (byte)b);
        }
    }

    initPaletteMedianCut();


    for (int y = 0, o = 0; y < H; y++)
    {
        for (int x = 0; x < W; x++, o++)
        {
            indexedImage[o] = rgb2IndexMedianCut(rgbImage[o]);
        }
    }

    for (int i = 0; i < 16; i++)
    {
        fout << (int)palette[i].r << " " << (int)palette[i].g << " " << (int)palette[i].b << endl;
    }

    for (int y = 0, o = 0; y < H; y++)
    {
        for (int x = 0; x < W; x++, o++)
        {
            if (x > 0) fout << " ";
            fout << (int)indexedImage[o];
        }
        fout << endl;
    }

    return 0;
}

void index2rgbImage()
{
    for (int y = 0, o = 0; y < H; y++)
    {
        for (int x = 0; x < W; x++, o++)
        {
            int i = indexedImage[o];
            rgbImage[o] = palette[i];
        }
    }
}

int decompress(ifstream& fin, ofstream& fout)
{
    for (int i = 0; i < 16; i++)
    {
        int r, g, b;
        fin >> r >> g >> b;
        if (r < 0 || r > 255 || g < 0 || g > 255 || b < 0 || b > 255)
        {
            cout << "invalid palette color at index: " << i << " : " << r << ", " << g << ", " << b << endl;
            return 1;
        }
        palette[i].set((byte)r, (byte)g, (byte)b);
    }

    fin >> W >> H;

    for (int y = 0, o = 0; y < H; y++)
    {
        for (int x = 0; x < W; x++, o++)
        {
            int i;
            fin >> i;
            if (i < 0 || i > 15)
            {
                cout << "invalid pixel index " << i << endl;
                return 2;
            }
            indexedImage[o] = i;
        }
    }

    index2rgbImage();

    for (int y = 0, o = 0; y < H; y++)
    {
        for (int x = 0; x < W; x++, o++)
        {
            auto& p = rgbImage[o];
            fout << (int)p.r << " " << (int)p.g << " " << (int)p.b << endl;
        }
    }
    return 0;
}

int execute(const char* inname, const char* outname)
{
    ifstream fin(inname);
    ofstream fout(outname);
    int mode;
    fin >> mode;
    if (mode == 0)
    {
        return compress(fin, fout);
    }
    else if(mode == 1)
    {
        return decompress(fin, fout);
    }
    else
    {
        cout << "invalid mode " << mode << endl;
        return 1;
    }
}

int main()
{
    return execute("imrec.in", "imrec.out");

    //for (int i = 0; i <= 6; i++)
    //{
    //    char iname[32], oname[32];
    //    sprintf(iname, "%02i.in", i);
    //    sprintf(oname, "%02i.out", i);
    //    execute(iname, oname);
    //    sprintf(iname, "%02i.in.bmp", i);
    //    saveBMP(iname);
    //    index2rgbImage();
    //    sprintf(oname, "%02i.out.bmp", i);
    //    saveBMP(oname);
    //}
}