// drawing.cpp : Defines the entry point for the console application.
//
#define DMP_BMP

#ifdef _MSC_VER
#include "stdafx.h"
#endif
#include <fstream>
#include <memory.h>
#include <list>
#include <memory>

using namespace std;
typedef unsigned char byte;

struct cmd;
struct image;
struct pallete;
typedef unique_ptr<cmd> cmd_ptr;
typedef list<cmd_ptr> cmd_list;
typedef cmd_list::iterator cmd_list_iter;

struct color
{
    byte b, g, r, a;
    color() { b = g = r = a = 255; }
    color(byte r_, byte g_, byte b_, byte a_ = 255)
        : b(b_), g(g_), r(r_), a(a_) { }

    int dist(color o) {
        return (r - o.r) * (r - o.r) + (g - o.g) * (g - o.g) + (b - o.b) + (b - o.b);
    }

    color mix(color o) {
        return color((r + o.r) / 2, (g + o.g) / 2 , (b + o.b) / 2);
    }
};

struct image
{
    int N;
    color p[90000];

    void read_color(istream& fin, byte color::*ptr, double& avg);
    void dmp_bmp(const char* file_name);
    color operator()(int x, int y) const { return p[x + y * N]; }
    color& operator()(int x, int y) { return p[x + y * N]; }
    void fill(cmd_list& commands);
    void fill_blocks(cmd_list& commands, pallete& pal);
    color average(int x1, int y1, int x2, int y2);
};

struct pallete
{
    int K;
    color p[12], avg, col;

    void read(istream& fin);

    void mix(cmd_list& commands, image& img, color target, int iters);
};

struct cmd
{
    virtual void print(ostream& out) const = 0;
    virtual void apply(image& img, pallete& pal) const = 0;
};

ostream& operator <<(ostream& out, const cmd& cmd)
{
    cmd.print(out);
    return out;
}

struct cmd_mix_p : cmd
{
    int i;
    cmd_mix_p(int i_) : i(i_) { }
    virtual void print(ostream& out) const { out << "1 " << i << endl; }
    virtual void apply(image& img, pallete& pal) const {
        pal.col = pal.col.mix(pal.p[i]);
    }
};

struct cmd_mix_xy : cmd
{
    int x, y;
    cmd_mix_xy(int x_, int y_) : x(x_), y(y_) { }
    virtual void print(ostream& out) const { out << "2 " << x << " " << y << endl; }
    virtual void apply(image& img, pallete& pal) const {
        pal.col = pal.col.mix(img(x, y));
    }
};

struct cmd_draw_x1y1x2y2 : cmd
{
    int x1, y1, x2, y2;
    cmd_draw_x1y1x2y2(int x1_, int y1_, int x2_, int y2_) : x1(x1_), y1(y1_), x2(x2_), y2(y2_) { }
    virtual void print(ostream& out) const { out << "3 " << x1 << " " << y1 << " " << x2 << " " << y2 << endl; }
    virtual void apply(image& img, pallete& pal) const {
        for (int y = y1; y <= y2; y++) {
            for(int x = x1; x <= x2; x++) {
                img(x, y) = pal.col;
            }
        }
    }
};

struct cmd_mix_x1y1x2y2 : cmd
{
    int x1, y1, x2, y2;
    cmd_mix_x1y1x2y2(int x1_, int y1_, int x2_, int y2_) : x1(x1_), y1(y1_), x2(x2_), y2(y2_) { }
    virtual void print(ostream& out) const { out << "4 " << x1 << " " << y1 << " " << x2 << " " << y2 << endl; }
    virtual void apply(image& img, pallete& pal) const {
        for (int y = y1; y <= y2; y++) {
            for(int x = x1; x <= x2; x++) {
                img(x, y) = pal.col.mix(img(x, y));
            }
        }
    }
};

#ifdef DMP_BMP

struct bmp_file_header {
    byte signature[2];
    unsigned int size;
    unsigned int reserved;
    unsigned int offset;
};

void write_int(const int in, byte* out) {
    memcpy(out, &in, 4);
}

void write_short(const short in, byte* out) {
    memcpy(out, &in, 2);
}

void image::dmp_bmp(const char* file_name) {
    const int bfh_size = 14, bih_size = 40;
    byte buff[bfh_size + bih_size];
    memset(buff, 0, sizeof(buff));
    int off = bih_size + bfh_size, size = N * N * 4 + off, res = 0; // size in dwords + file header + core header
    // write bmp file header
    buff[0] = 'B';
    buff[1] = 'M';
    write_int(size, buff + 2);
    write_int(res, buff + 6);
    write_int(off, buff + 10);

    // write bmp info header
    write_int(bih_size, buff + 14);
    write_int(N, buff + 18);
    write_int(-N, buff + 22);
    write_short(1, buff + 26);
    write_short(32, buff + 28);
    write_int(0, buff + 30); // BI_RGB = 0 - no compression
    write_int(0, buff + 34); // size = 0 for BI_RGB
    write_int(2835, buff + 38); // X DPI
    write_int(2835, buff + 42); // Y DPI
    write_int(0, buff + 46); // colors = 0
    write_int(0, buff + 50); // important colors = 0

    ofstream fout;
    fout.open(file_name, ios::binary | ios::out);
    fout.write((char*)buff, sizeof(buff));
    fout.write((char*)p, N * N * 4);
    fout.close();
}
#else
void image::dmp_bmp(const char* file_name) {
}
#endif

void pallete::read(istream& fin)
{
    auto pt = p;
    for (int i = 0; i < K; i++, pt++) {
        int r, g, b;
        fin >> r >> g >> b;
        pt->r = r;
        pt->g = g;
        pt->b = b;
    }
}

void image::read_color(istream& fin, byte color::*ptr, double& avg)
{
    avg = 0;
    auto pt = p;
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            int color;
            fin >> color;
            pt++->*ptr = (byte)color;
            avg += color;
        }
    }
    avg /= N * N;
}

color image::average(int x1, int y1, int x2, int y2) {
    double r = 0, g = 0, b = 0;
    for (int y = y1; y <= y2; y++) {
        for(int x = x1; x <= x2; x++) {
            color c = (*this)(x, y);
            r += c.r;
            g += c.g;
            b += c.b;
        }
    }
    int pts = (y2 - y1 + 1) * (x2 - x1 + 1);
    r /= pts;
    g /= pts;
    b /= pts;
    return color((byte)r, (byte)g, (byte)b);
}

void image::fill(cmd_list& commands) {
    for (int y = 0; y < N; y += 10) {
        for (int x = 0; x < N; x += 20) {
            commands.push_back(cmd_ptr(new cmd_draw_x1y1x2y2(x, y, min(x + 19, N - 1), min(y + 9, N - 1))));
        }
    }
}

void image::fill_blocks(cmd_list& commands, pallete& pal) {
    for (int y = 0; y < N; y += 10) {
        for (int x = 0; x < N; x += 10) {
            int x2 = min(x + 19, N - 1);
            int y2 = min(y + 9, N - 1);
            color c = average(x, y, x2, y2);
            pal.mix(commands, *this, c, 16);
            commands.push_back(cmd_ptr(new cmd_draw_x1y1x2y2(x, y, x2, y2)));
            commands.back()->apply(*this, pal);
        }
    }
}

void pallete::mix(cmd_list& commands, image& img, color target, int iters) {
    int min_dist = target.dist(col);
    for (int it = 0; it < iters; it++) {
        int min_i = -1;
        for(int i = 0; i < K; i++) {
            int dist = col.mix(p[i]).dist(target);
            if ( dist < min_dist) {
                min_dist = dist;
                min_i = i;
            }
        }
        if (min_i >= 0)
        {
            commands.push_back(cmd_ptr(new cmd_mix_p(min_i)));
            commands.back()->apply(img, *this);
        }
        else
            break;
    }
}


void read_in(const char* file_name, image& img, pallete& pal)
{
    ifstream fin;
    fin.open(file_name);
    fin >> img.N >> pal.K;
    // read pallete
    pal.read(fin);
    // read image
    double ar, ag, ab;
    img.read_color(fin, &color::r, ar);
    img.read_color(fin, &color::g, ag);
    img.read_color(fin, &color::b, ab);
    fin.close();

    pal.avg.r = (byte)ar;
    pal.avg.g = (byte)ag;
    pal.avg.b = (byte)ab;
}

void dump_as_bmp(const char* in_name, const char* out_name)
{
    image img;
    pallete pal;
    read_in(in_name, img, pal);
    img.dmp_bmp(out_name);
}

void dump_as_bmps()
{
    dump_as_bmp("drawing.01.in", "drawing.01.bmp");
    dump_as_bmp("drawing.02.in", "drawing.02.bmp");
    dump_as_bmp("drawing.03.in", "drawing.03.bmp");
}

int process(const char* in_name, const char* out_name)
{
    image img;
    pallete pal;
    read_in(in_name, img, pal);

    cmd_list cmds;
    //pal.mix(cmds, pal.avg, 6);
    //img.fill(cmds);
    img.fill_blocks(cmds, pal);

    ofstream fout;
    fout.open(out_name);
    fout << cmds.size() << endl;
    for(cmd_list_iter b(cmds.begin()), e(cmds.end()); b != e; b++) {
        (*b)->print(fout);
    }
    fout.close();
    return 0;
}

int main()
{
    //dump_as_bmps();
    //return 0;
    return process("drawing.in", "drawing.out");
}