高精板子

```cpp
struct bign {
  int d[MaxM], len;

  void clean() {
    while (len > 1 && !d[len - 1]) len--;
  }

  bign() {
    fill(d, d + MaxM, 0);
    len = 1;
  }
  bign(int num) { *this = num; }
  bign(string num) { *this = num; }

  bign operator=(const string num) {
    fill(d, d + MaxM, 0);
    len = num.size();
    for (int i = 0; i < len; i++) d[i] = num[len - 1 - i] - '0';
    clean();
    return *this;
  }

  bign operator=(int num) {
    string s;
    for (; num; num /= 10) s = char(num % 10 + '0') + s;
    *this = s;
    return *this;
  }

  bign operator+(const bign& b) {
    bign c = *this;
    int cnt;
    for (cnt = 0; cnt < b.len; cnt++) {
      c.d[cnt] += b.d[cnt];
      c.d[cnt + 1] += c.d[cnt] / 10, c.d[cnt] %= 10;
    }
    while (c.d[cnt] > 9) c.d[cnt++] %= 10, c.d[cnt]++;
    c.len = max(len, b.len);
    if (c.d[cnt] && c.len <= cnt) c.len = cnt + 1;
    return c;
  }

  bign operator-(const bign& b) {
    bign c = *this;
    int cnt;
    for (cnt = 0; cnt < b.len; cnt++) {
      c.d[cnt] -= b.d[cnt];
      if (c.d[cnt] < 0) c.d[cnt] += 10, c.d[cnt + 1]--;
    }
    while (c.d[cnt] < 0) c.d[cnt++] += 10, c.d[cnt]--;
    c.clean();
    return c;
  }

  bign operator*(const bign& b) const {
    bign c;
    c.len = len + b.len + 2;
    for (int i = 0; i < len; i++)
      for (int j = 0; j < b.len; j++)
        c.d[i + j] += d[i] * b.d[j];
    for (int i = 0; i < c.len - 1; i++)
      c.d[i + 1] += c.d[i] / 10, c.d[i] %= 10;
    c.clean();
    return c;
  }

  bign operator/(const bign& b) {
    bign c = *this, a = 0;
    for (int i = len - 1, j; i >= 0; i--) {
      a = a * 10 + d[i];
      for (j = 0; j < 10; j++)
        if (a < b * (j + 1)) break;
      c.d[i] = j;
      a = a - b * j;
    }
    c.clean();
    return c;
  }

  bign operator%(const bign& b) {
    bign a = 0;
    for (int i = len - 1, j; i >= 0; i--) {
      a = a * 10 + d[i];
      for (j = 0; j < 10; j++)
        if (a < b * (j + 1)) break;
      a = a - b * j;
    }
    return a;
  }

  bign operator+=(const bign& b) {
    *this = *this + b;
    return *this;
  }

  bool operator<(const bign& b) const {
    if (len != b.len) return len < b.len;
    for (int i = len - 1; i >= 0; i--)
      if (d[i] != b.d[i]) return d[i] < b.d[i];
    return false;
  }
  bool operator>(const bign& b) const { return b < *this; }
  bool operator<=(const bign& b) const { return !(b < *this); }
  bool operator>=(const bign& b) const { return !(*this < b); }
  bool operator!=(const bign& b) const { return b < *this || *this < b; }
  bool operator==(const bign& b) const { return !(b < *this) && !(b > *this); }

  string str() const {
    string s(len, '0');
    for (int i = 0; i < len; i++) s[len - 1 - i] = d[i] + '0';
    return s;
  }

  friend istream& operator>>(istream& in, bign& x) {
    string s;
    in >> s;
    x = s.c_str();
    return in;
  }

  friend ostream& operator<<(ostream& out, const bign& x) {
    out << x.str();
    return out;
  }
} f[MaxN], k;