use rayon::join;
use std::{
    io::{stdin, stdout, Read, Write},
    time::Instant,
};

const WIDTH: usize = 1920;
const HEIGHT: usize = 1080;

fn main() {
    let mut oframe = Frame::new();
    let mut dframe = Frame::new();
    let mut out = Vec::<u8>::new();
    let do_debug = false;
    loop {
        let timer = Instant::now();
        let iframe = Frame::read(stdin());

        let t = encode(&oframe, &iframe, Area::root());
        decode(&mut oframe, Area::root(), &t);

        write(&mut out, &t);

        if do_debug {
            dframe.0.copy_from_slice(&oframe.0);
            debug(&mut dframe, Area::root(), &t);
            dframe.write(stdout());
        } else {
            oframe.write(stdout());
        }

        eprintln!(
            "compression={:.01} time={:?}",
            (WIDTH * HEIGHT * 3) as f64 / out.len() as f64,
            timer.elapsed()
        );
        out.clear();
    }
}

pub fn write(w: &mut Vec<u8>, t: &DiffTree) {
    match t {
        DiffTree::Split([a, b]) => {
            w.push(0);
            write(w, a);
            write(w, b);
        }
        DiffTree::Diff(d) => w.extend([1, d.0[0] as u8, d.0[1] as u8, d.0[2] as u8]),
    }
}

pub fn decode(f: &mut Frame, area: Area, tree: &DiffTree) {
    match tree {
        DiffTree::Split([ta, tb]) => {
            let (aa, ab) = area.split();
            decode(f, aa, ta);
            decode(f, ab, tb);
        }
        DiffTree::Diff(diff) => {
            f.apply_area_diff(area, *diff);
        }
    }
}
pub fn debug(f: &mut Frame, area: Area, tree: &DiffTree) {
    match tree {
        DiffTree::Split([ta, tb]) => {
            let (aa, ab) = area.split();
            decode(f, aa, ta);
            decode(f, ab, tb);
        }
        DiffTree::Diff(_diff) => {
            let Area { x1, y1, x2, y2 } = area;
            for x in x1..x2 {
                for y in y1..y2 {
                    let o = (x + y * WIDTH) * 3;
                    f.0[o + 0] = 255;
                    f.0[o + 1] = 0;
                    f.0[o + 2] = 255;
                }
            }
        }
    }
}

pub fn encode(a: &Frame, b: &Frame, area: Area) -> DiffTree {
    if area.area() == 1 {
        DiffTree::Diff(Frame::diff_pixel(a, b, area.x1, area.y1))
    } else {
        let (aa, ba) = area.split();
        let (at, bt) = join(|| encode(a, b, aa), || encode(a, b, ba));

        match (&at, &bt) {
            (DiffTree::Diff(ad), DiffTree::Diff(bd)) => {
                let d_r = ad.0[0].abs_diff(bd.0[0]);
                let d_g = ad.0[1].abs_diff(bd.0[1]);
                let d_b = ad.0[2].abs_diff(bd.0[2]);

                let visdiff = (d_r as usize + d_g as usize + d_b as usize) * aa.area();
                if visdiff < 100 {
                    return DiffTree::Diff(PixelDiff([
                        ((ad.0[0] as i16 + bd.0[0] as i16) / 2) as i8,
                        ((ad.0[1] as i16 + bd.0[1] as i16) / 2) as i8,
                        ((ad.0[2] as i16 + bd.0[2] as i16) / 2) as i8,
                    ]));
                }
            }
            _ => (),
        }
        DiffTree::Split([Box::new(at), Box::new(bt)])
    }
}

pub enum DiffTree {
    Split([Box<DiffTree>; 2]),
    Diff(PixelDiff),
}

#[derive(Debug)]
pub struct Frame(Vec<u8>);
#[derive(Debug, Clone, Copy)]
pub struct PixelDiff([i8; 3]);
#[derive(Debug, Clone, Copy)]
pub struct Area {
    x1: usize,
    y1: usize,
    x2: usize,
    y2: usize,
}

#[inline]
fn diff_clamp(x: u8, y: u8) -> i8 {
    if y >= x {
        (y - x).min(127) as i8
    } else {
        -((x - y).min(128) as i8)
    }
}

impl Frame {
    pub fn new() -> Self {
        Self(vec![0u8; WIDTH * HEIGHT * 3])
    }
    pub fn read(mut r: impl Read) -> Self {
        let mut f = Frame::new();
        r.read_exact(&mut f.0).unwrap();
        f
    }
    pub fn write(&self, mut w: impl Write) {
        w.write_all(&self.0).unwrap()
    }

    pub fn diff_pixel(a: &Frame, b: &Frame, x: usize, y: usize) -> PixelDiff {
        let o = (x + y * WIDTH) * 3;
        PixelDiff([
            diff_clamp(a.0[o + 0], b.0[o + 0]),
            diff_clamp(a.0[o + 1], b.0[o + 1]),
            diff_clamp(a.0[o + 2], b.0[o + 2]),
        ])
    }

    pub fn apply_area_diff(&mut self, Area { x1, y1, x2, y2 }: Area, p: PixelDiff) {
        for x in x1..x2 {
            for y in y1..y2 {
                let o = (x + y * WIDTH) * 3;
                self.0[o + 0] = self.0[o + 0].saturating_add_signed(p.0[0]);
                self.0[o + 1] = self.0[o + 1].saturating_add_signed(p.0[1]);
                self.0[o + 2] = self.0[o + 2].saturating_add_signed(p.0[2]);
            }
        }
    }
    // pub fn average_area_diff(
    //     &self,
    //     other: &Frame,
    //     area @ Area { x1, y1, x2, y2 }: Area,
    // ) -> PixelDiff {
    //     let (mut r, mut g, mut b) = (0i32, 0i32, 0i32);
    //     for x in x1..x2 {
    //         for y in y1..y2 {
    //             let o = (x + y * WIDTH) * 3;
    //             r += other.0[o + 0] as i32 - self.0[o + 0] as i32;
    //             g += other.0[o + 1] as i32 - self.0[o + 1] as i32;
    //             b += other.0[o + 2] as i32 - self.0[o + 2] as i32;
    //         }
    //     }
    //     let a = area.area() as i32;
    //     PixelDiff([
    //         (r / a).clamp(i8::MIN as i32, i8::MAX as i32) as i8,
    //         (g / a).clamp(i8::MIN as i32, i8::MAX as i32) as i8,
    //         (b / a).clamp(i8::MIN as i32, i8::MAX as i32) as i8,
    //     ])
    // }
}
impl Area {
    pub fn area(&self) -> usize {
        self.width() as usize * self.height() as usize
    }
    pub fn width(&self) -> usize {
        self.x2 - self.x1
    }
    pub fn height(&self) -> usize {
        self.y2 - self.y1
    }
    pub fn root() -> Self {
        Area {
            x1: 0,
            y1: 0,
            x2: WIDTH,
            y2: HEIGHT,
        }
    }
    pub fn split(&self) -> (Self, Self) {
        let Area { x1, y1, x2, y2 } = *self;
        if self.width() > self.height() {
            let xm = (self.x1 + self.x2) / 2;
            (Self { x1, x2: xm, y1, y2 }, Self { x1: xm, x2, y1, y2 })
        } else {
            let ym = (self.y1 + self.y2) / 2;
            (Self { x1, x2, y1, y2: ym }, Self { x1, x2, y1: ym, y2 })
        }
    }
}