// #include <bitops>
#include <i8>

struct u16 {
  // big-endian?
  cell n1;
  cell n0;
}

fn _0(struct u16 n)     {n.n1 = 0;   n.n0 = 0;}
fn _1(struct u16 n)     {n.n1 = 0;   n.n0 = 1;}
fn _10(struct u16 n)    {n.n1 = 0;   n.n0 = 10;}
fn _100(struct u16 n)   {n.n1 = 0;   n.n0 = 100;}
fn _200(struct u16 n)   {n.n1 = 0;   n.n0 = 200;}
fn _300(struct u16 n)   {n.n1 = 1;   n.n0 = 44;}
fn _1000(struct u16 n)  {n.n1 = 3;   n.n0 = 232;}
fn _2(struct u16 n)     {n.n1 = 0;   n.n0 = 2;}
fn _4(struct u16 n)     {n.n1 = 0;   n.n0 = 4;}
fn _8(struct u16 n)     {n.n1 = 0;   n.n0 = 8;}
fn _16(struct u16 n)    {n.n1 = 0;   n.n0 = 16;}
fn _32(struct u16 n)    {n.n1 = 0;   n.n0 = 32;}
fn _64(struct u16 n)    {n.n1 = 0;   n.n0 = 64;}
fn _128(struct u16 n)   {n.n1 = 0;   n.n0 = 128;}
fn _256(struct u16 n)   {n.n1 = 1;   n.n0 = 0;}
fn _512(struct u16 n)   {n.n1 = 2;   n.n0 = 0;}
fn _1024(struct u16 n)  {n.n1 = 4;   n.n0 = 0;}
fn _2048(struct u16 n)  {n.n1 = 8;   n.n0 = 0;}
fn _4096(struct u16 n)  {n.n1 = 16;  n.n0 = 0;}
fn _8192(struct u16 n)  {n.n1 = 32;  n.n0 = 0;}
fn _16384(struct u16 n) {n.n1 = 64;  n.n0 = 0;}
fn _10000(struct u16 n) {n.n1 = 39;  n.n0 = 16;}
fn _20000(struct u16 n) {n.n1 = 78;  n.n0 = 32;}
fn _30000(struct u16 n) {n.n1 = 117; n.n0 = 48;}
fn _40000(struct u16 n) {n.n1 = 156; n.n0 = 64;}
fn _50000(struct u16 n) {n.n1 = 195; n.n0 = 80;}
fn _60000(struct u16 n) {n.n1 = 234; n.n0 = 96;}
fn _65280(struct u16 n) {n.n1 = 255; n.n0 = 0;}
fn _65535(struct u16 n) {n.n1 = 255; n.n0 = 255;}

fn MAX(struct u16 n) {_65535(n);}

/// set one u16 to be a copy of another
fn set(struct u16 dest, struct u16 src) {
  dest.n0 = src.n0;
  dest.n1 = src.n1;
}
/// set overload for u8
fn set(struct u16 dest, cell src) {
  dest.n0 = src;
  dest.n1 = 0;
}
/// set destructively
fn set_d(struct u16 dest, struct u16 src) {
  dest.n0 = 0;
  drain src.n0 into dest.n0;
  dest.n1 = 0;
  drain src.n1 into dest.n1;
}

/// increment a u16 by 1
fn inc(struct u16 self) {
  self.n0 += 1;
  self.n1 += 1;
  if self.n0 {
    self.n1 -= 1;
  }
  // more efficient version of the following:
  // if not self.n0 {
  //   self.n1 += 1;
  // }
}

/// decrement a u16 by 1
fn dec(struct u16 self) {
  self.n1 -= 1;
  if self.n0 {
    self.n1 += 1;
  }
  self.n0 -= 1;
}

/// add a cell's value as a u8 in place to the current u16
fn add(struct u16 self, cell other) {
  copy other {
    inc(self);
  }
}
/// overload for an i8 (signed 8-bit)
fn add(struct u16 self, struct i8 other) {
  cell abs;
  cell neg;
  to_u8(other, abs, neg);

  if not neg {
    drain abs {
      inc(self);
    }
  } else {
    drain abs {
      dec(self);
    }
  }
  assert abs equals 0;
}
/// overload for another u16
fn add(struct u16 self, struct u16 other) {
  // most significant first
  self.n1 += other.n1;
  copy other.n0 {
    self.n0 += 1;
    self.n1 += 1;
    if self.n0 {
      self.n1 -= 1;
    }
  }
}

/// subtract a cell as a u8 from the current u16
fn sub(struct u16 self, cell other) {
  copy other {
    dec(self);
  }
}
// subtract overload for another u16
fn sub(struct u16 self, struct u16 other) {
  self.n1 -= other.n1;
  copy other.n0 {
    self.n1 -= 1;
    if self.n0 {
      self.n1 += 1;
    }
    self.n0 -= 1;
  }
}

/// check if number is non-zero
fn ne_zero(struct u16 self, cell _output) {
  _output = false;
  // return n0 || n1
  if self.n0 {
    _output = true;
  }
  if self.n1 {
    _output = true;
  }
}

/// shift the numbers base-10 digits left, by multiplying by 10
fn mult_10(struct u16 self) {
  // naively multiply by 10
  // it is unclear if there is a better way with bitshifts
  struct u16 n;
  set(n, self);
  drain 9 {
    add(self, n);
  }
}

/// divide by 10
fn div_10(struct u16 self) {
  struct u16 quotient;
  cell dividing = true;
  while dividing {
    drain 10 {
      cell o; ne_zero(self, o);
      if o {
        dec(self);
      } else {
        // remainder += 1;
        dividing = false;
      }
    }
    if dividing {
      inc(quotient);
    }
  }
  set_d(self, quotient);
}

/// lazy implementation of a divide by 2
// TODO: make more efficient
fn div_2(struct u16 self) {
  struct u16 quotient;
  cell dividing = true;
  while dividing {
    drain 2 {
      cell o; ne_zero(self, o);
      if o {
        dec(self);
      } else {
        // remainder += 1;
        dividing = false;
      }
    }
    if dividing {
      inc(quotient);
    }
  }
  set_d(self, quotient);
}

/// multiply by 25, drains n
fn mult_n_d(struct u16 self, cell n) {
  struct u16 c;
  set(c, self);
  n -= 1;
  drain n {
    add(self, c);
  }
}

/// print the binary
fn debug(struct u16 self) {
  debug(self.n1);
  debug(self.n0);
}

/// print the u16 as a base-10 natural number [0, 65535]
fn print(struct u16 self) {
  struct DS {
    // markers either side of the digit stack
    // cell m0 @0;
    cell[5] stack;
    // cell m1 @6;
  }
  struct DS ds;
  fn shift_stack() {
    ds.stack[4] = 0;
    drain ds.stack[3] into ds.stack[4];
    drain ds.stack[2] into ds.stack[3];
    drain ds.stack[1] into ds.stack[2];
    drain ds.stack[0] into ds.stack[1];
  }
  fn unshift_stack() {
    ds.stack[0] = 0;
    drain ds.stack[1] into ds.stack[0];
    drain ds.stack[2] into ds.stack[1];
    drain ds.stack[3] into ds.stack[2];
    drain ds.stack[4] into ds.stack[3];
  }
  fn debug_stack() {
    output ds.stack[0] + '0';
    output ds.stack[1] + '0';
    output ds.stack[2] + '0';
    output ds.stack[3] + '0';
    output ds.stack[4] + '0';
  }

  struct u16 n;
  set(n, self);
  // essentially repeatedly divide by 10
  drain 5 {
    shift_stack();
    cell dividing = true;
    struct u16 m;// MAX(m); // quotient set to -1 = 65535
    ds.stack[0] = 10; // remainder, add 1 for magic later on
    while dividing {
      drain 10 {
        cell o; ne_zero(n, o);
        if o {
          dec(n);
        } else {
          ds.stack[0] -= 1;
          dividing = false;
        }
      }

      if dividing {
        inc(m);
      }
    }
    // copy new quotient to value so we start again
    set_d(n, m);
  }

// debug_stack(); output 10;
  {
    cell not_leading = false;
    drain 4 {
      if ds.stack[0] {
        not_leading = true;
      }
      if not_leading {
        ds.stack[0] += '0';
        output ds.stack[0];
      }
      unshift_stack();
    }
  }
  ds.stack[0] += '0';
  output ds.stack[0];
}

/// read a u16 number from stdin, assumes n = 0 and valid newline-terminated input
fn read(struct u16 n) {
  cell digit;
  input digit;
  digit -= '\n';
  while digit {
    digit += '\n' - '0';
    // shift digits (times by 10) and add the new digit
    mult_10(n);
    add(n, digit);

    input digit;
    digit -= '\n';
  }
}

// debug/test code:
// struct u16 s; _20000(s);
// output "s = "; print(s); output " ("; debug(s); output ")\n";
// div_10(s); output "s/10 = "; print(s); output " ("; debug(s); output ")\n";
// div_10(s); output "s/10 = "; print(s); output " ("; debug(s); output ")\n";
// div_10(s); output "s/10 = "; print(s); output " ("; debug(s); output ")\n";
// div_10(s); output "s/10 = "; print(s); output " ("; debug(s); output ")\n";
// div_10(s); output "s/10 = "; print(s); output " ("; debug(s); output ")\n";

// #include <u8>
// struct u16 j;
// struct u16 k; _256(k);
// read(j);
// print(j); output '\n';

// struct u16 a;
// output "a = "; print(a); output "\n";
// MAX(a);
// output "(a = "; print(a); output ")\n";
// cell c = 5;
// output "(c = 5)\n";
// add(a, c);
// output "(a += c)\n";
// output "a = "; print(a); output "\n";
// struct u16 b;
// _100(a);
// output "(a = "; print(a); output ")\n";
// _1000(b);
// output "(b = "; print(b); output ")\n";
// add(a, b);
// output "(a += b)\n";
// output "a = "; print(a); output '\n';
// _16384(b);
// output "(b = "; print(b); output ")\n";
// add(a, b);
// output "(a += b)\n";
// output "a = "; print(a); output '\n';
// _50000(b);
// output "(b = "; print(b); output ")\n";
// add(a, b);
// output "(a += b)\n";
// output "a = "; print(a); output '\n';

// struct u16 m; m.n0 = 1;
// struct u16 n; n.n0 = 0;
// print(m); output 10;
// sub(m, n); output "-"; print(n); output ": "; print(m); output "\n";
// _1(n);
// sub(m, n); output "-"; print(n); output ": "; print(m); output "\n";
// sub(m, n); output "-"; print(n); output ": "; print(m); output "\n";
// add(m, n); output "+"; print(n); output ": "; print(m); output "\n";
// _0(n); n.n1 = 1;
// sub(m, n); output "-"; print(n); output ": "; print(m); output "\n";

// output '\n';
// struct u16 x; _10(x);
// cell y = 4;
// print(x); output " - "; print(y); output " = ";
// sub(x, y);
// print(x); output "\n";
// y = 45;
// print(x); output " - "; print(y); output " = ";
// sub(x, y);
// print(x); output "\n";
// print(x); output " + "; print(y); output " = ";
// add(x, y);
// print(x); output "\n";
// _50000(x);
// y = 239;
// print(x); output " - "; print(y); output " = ";
// sub(x, y);
// print(x); output "\n";
// struct u16 z; _40000(z);
// print(x); output " - "; print(z); output " = ";
// sub(x, z);
// print(x); output "\n";
// _10000(z);
// print(x); output " - "; print(z); output " = ";
// sub(x, z);
// print(x); output "\n";
// z.n0 = 0; z.n1 = 0;
// y = 239;
// sub(z, y);
// print(x); output " - "; print(z); output " = ";
// sub(x, z);
// print(x); output "\n";
