simple bignum for c++

const int BASE = 1e9;

struct Int {
  vector<int> v;
  Int(int x = 0) {
    if (x == 0) {
      v.resize(1);
      return;
    }
    while (x) {
      v.push_back(x % BASE);
      x /= BASE;
    }
  }
  Int(string s) {
    reverse(all(s));
    while (s.size() % 9) s += '0';
    reverse(all(s));
    for (int i = s.size() - 9; i >= 0; i -= 9) {
      v.push_back(stoi(s.substr(i, 9)));
    }
  }
  void Rlz() {
    while (v.size() > 1 && v.back() == 0) v.pop_back();
  }
};

Int operator+(Int a, Int b) {
  while ((int)(a.v.size()) < (int)(b.v.size())) a.v.push_back(0);
  while ((int)(a.v.size()) > (int)(b.v.size())) b.v.push_back(0);
  Int c; c.v.resize(max((int)(a.v.size()), (int)(b.v.size())));
  int g = 0;
  for (int i = 0; i < (int)(c.v.size()); i++) {
    if (i < (int)(a.v.size())) g += a.v[i];
    if (i < (int)(b.v.size())) g += b.v[i];
    c.v[i] = g % BASE;
    g /= BASE;
  }
  if (g > 0) c.v.push_back(1);
  c.Rlz();
  return c;
}

Int operator*(Int a, Int b) {
  Int c; c.v.resize((int)(a.v.size()) + (int)(b.v.size()));
  for (int i = 0; i < (int)(a.v.size()); i++) {
    int g = 0;
    for (int j = 0; j < (int)(b.v.size()); j++) {
      g += c.v[i + j] + a.v[i] * b.v[j];
      c.v[i + j] = g % BASE;
      g /= BASE;
    }
    if (g > 0) c.v[i + (int)(b.v.size())] += g;
  }
  c.Rlz();
  return c;
}

Int operator-(Int a, Int b) {
  Int c; c.v.resize((int)(a.v.size()));
  while ((int)(a.v.size()) > (int)(b.v.size())) b.v.push_back(0);
  int g = 0;
  for (int i = 0; i < (int)(a.v.size()); i++) {
    g += a.v[i] - b.v[i];
    if (g >= 0) c.v[i] = g, g = 0;
    else c.v[i] = g + BASE, g = -1;
  }
  c.Rlz();
  return c;
}

bool operator<(Int a, Int b) {
  if ((int)(a.v.size()) != (int)(b.v.size())) {
    return (int)(a.v.size()) < (int)(b.v.size());
  }
  for (int i = (int)((int)(a.v.size())) - 1; i >= 0; i--) {
    if (a.v[i] != b.v[i]) return a.v[i] < b.v[i];
  }
  return 0;
}

bool operator==(Int a, Int b) {
  if ((int)(a.v.size()) != (int)(b.v.size())) return 0;
  for (int i = 0; i < (int)(a.v.size()); i++) {
    if (a.v[i] != b.v[i]) return 0;
  }
  return 1;
}

ostream& operator<<(ostream& os, Int x) {
  os << x.v.back();
  for (int i = (int)(x.v.size()) - 2; i >= 0 ; i--) {
    cout << setw(9) << setfill('0') << x.v[i];
  }
  return os;
}

istream& operator>>(istream& is, Int& x) {
  string s;
  cin >> s;
  x = Int(s);
  return is;
}