```
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

class Bigint {
private:
  vector<long long> num;
  bool sign;
  static constexpr long long BASE = 100000000000000000LL;
  long long safe_at(size_t index) const;
  double safe_log10(const long long &a) const;
  Bigint Karatsuba_algorithm(const Bigint &a, const Bigint &b) const;

public:
  Bigint multi(const Bigint &a, const Bigint &b) const;
  Bigint(string str_num = "0");
  Bigint(vector<long long> vec, bool sign = true);
  string str() const;
  bool operator==(const Bigint &b) const;
  bool operator<(const Bigint &b) const;
  bool operator>(const Bigint &b) const;
  bool operator<=(const Bigint &b) const;
  bool operator>=(const Bigint &b) const;
  Bigint operator!() const;
  Bigint operator+(const Bigint &b) const;
  Bigint operator-(const Bigint &b) const;
  Bigint operator*(const Bigint &b) const;
  pair<Bigint, Bigint> operator/(const Bigint &b) const;
};

long long Bigint::safe_at(size_t index) const {
  return (index < num.size()) ? num[index] : 0;
}
double Bigint::safe_log10(const long long &a) const { return log10(a ? a : 1); }
Bigint::Bigint(string str_num) : sign(str_num[0] != '-') {
  if (str_num[0] == '-')
    str_num = str_num.substr(1);
  int start = (str_num.size() - 1) % 17 + 1;
  this->num.resize(ceil(str_num.size() / 17));

  this->num[0] = stoll(str_num.substr(0, start));
  for (size_t i = 1; i < this->num.size(); i++) {
    this->num[i] = stoll(str_num.substr(17 * (i - 1) + start, 17));
  }
}
Bigint::Bigint(vector<long long> vec, bool sign) : num(vec), sign(sign) {}
Bigint Bigint::multi(const Bigint &a, const Bigint &b) const {
  if ((a.num.size() == 1 && a.num[0] == 0) ||
      (b.num.size() == 1 && b.num[0] == 0))
    return Bigint("0");
  vector<long long> result(
      static_cast<int>(floor(safe_log10(a.num[0]) + safe_log10(b.num[0])) / 17 +
                       a.num.size() + b.num.size() - 1),
      0);
  if (result.size() == 1)
    return Bigint({a.num.back() * b.num.back()}, !(this->sign ^ b.sign));
  for (size_t i = 0; i < a.num.size(); i++) {
    string n = to_string(a.num[a.num.size() - 1 - i]);
    int n_size = n.size();
    for (size_t j = 0; j < b.num.size(); j++) {
      long long m = b.num[b.num.size() - 1 - j];
      for (size_t l = 0; l < n_size; l++) {
        long long product = (n[l] - 48) * m;
        long long digitCount = pow(10, n_size - 1 - l);
        long long mask = static_cast<long long>(BASE / digitCount);
        result[i + j] += (product % mask) * digitCount;
        if (i + j + 1 < result.size()) {
          result[i + j + 1] += static_cast<long long>(product / mask);
          result[i + j + 1] += static_cast<long long>(result[i + j] / BASE);
          result[i + j] = result[i + j] % BASE;
        }
      }
    }
  }
  if (result.back() == 0)
    result.pop_back();
  reverse(result.begin(), result.end());
  return Bigint(result, !(this->sign ^ b.sign));
};
Bigint Bigint::Karatsuba_algorithm(const Bigint &a, const Bigint &b) const {
  int a_size = a.num.size(), b_size = b.num.size();
  int a_digit = a_size * 17 - 16 + floor(safe_log10(a.num[0])),
      b_digit = b_size * 17 - 16 + floor(safe_log10(b.num[0]));
  if (a_digit < b_digit)
    return Karatsuba_algorithm(b, a);
  if (a_size < 12 || b_size < 12)
    return multi(a, b);
  int half = a_digit / 2;
  Bigint a1(a.str().substr(0, half));
  Bigint a0(a.str().substr(half));
  Bigint b1(b.str().substr(0, half));
  Bigint b0(b.str().substr(half));

  Bigint z0(Karatsuba_algorithm(a1, b1).str());
  Bigint z1 = Karatsuba_algorithm(a0, b0);
  Bigint z2((Karatsuba_algorithm(a0 + a1, b0 + b1) - z0 - z1).str() +
            string(a_digit - half, '0'));
  Bigint result(Bigint(z0.str() + string((a_digit - half) * 2, '0')) + z1 + z2);
  return result;
}
string Bigint::str() const {
  stringstream ss;
  if (num.size() == 1 && num[0] == 0)
    return "0";
  if (!sign)
    ss << "-";
  ss << num[0] << setfill('0');
  for (size_t i = 1; i < num.size(); i++)
    ss << setw(17) << num[i];
  return ss.str();
}
bool Bigint::operator==(const Bigint &b) const { return num == b.num; }
bool Bigint::operator<(const Bigint &b) const {
  if (num.size() == b.num.size()) {
    for (size_t i = 0; i < num.size(); i++) {
      if (num[i] != b.num[i])
        return num[i] < b.num[i];
    }
  }
  return num.size() < b.num.size();
}
bool Bigint::operator>(const Bigint &b) const { return b < *this; }
bool Bigint::operator<=(const Bigint &b) const { return !(*this > b); }
bool Bigint::operator>=(const Bigint &b) const { return !(*this < b); }
Bigint Bigint::operator!() const { return Bigint(this->num, !(this->sign)); }
Bigint Bigint::operator+(const Bigint &b) const {
  if (sign != b.sign) {
    if (*this == b)
      return Bigint("0");
    return Bigint((*this - !b).num, (*this < b) ? b.sign : this->sign);
  }
  vector<long long> result(max(num.size(), b.num.size()));
  bool carry = false;
  for (size_t i = 0; i < result.size(); i++) {
    result[i] =
        safe_at(num.size() - 1 - i) + b.safe_at(b.num.size() - 1 - i) + carry;
    carry = (result[i] >= BASE);
    if (carry)
      result[i] -= BASE;
  }
  reverse(result.begin(), result.end());
  return Bigint(result, this->sign);
}
Bigint Bigint::operator-(const Bigint &b) const {
  if (sign != b.sign)
    return Bigint((*this + !b).num, this->sign);
  else if (*this == b)
    return Bigint("0");
  if (*this < b)
    return b - *this;

  vector<long long> result(max(num.size(), b.num.size()));
  bool carry = false;
  for (size_t i = 0; i < result.size(); i++) {
    result[i] =
        safe_at(num.size() - 1 - i) - b.safe_at(b.num.size() - 1 - i) - carry;
    carry = (result[i] < 0);
    if (carry)
      result[i] += BASE;
  }
  reverse(result.begin(), result.end());
  return Bigint(result, this->sign);
}
Bigint Bigint::operator*(const Bigint &b) const {
  return Karatsuba_algorithm(*this, b);
}
pair<Bigint, Bigint> Bigint::operator/(const Bigint &b) const {
  if (b == Bigint("0"))
    throw runtime_error("Division by zero");
  else if (b == Bigint("1"))
    return make_pair(*this, Bigint("0"));

  Bigint abs_this = Bigint(this->num, true);
  Bigint abs_b = Bigint(b.num, true);

  if (abs_this < abs_b) {
    return make_pair(Bigint("0"), *this);
  }

  Bigint left;
  Bigint right = abs_this;
  Bigint mid, product;
  Bigint one("1"), five("5");

  while (left <= right) {
    string mid_temp = ((left + right) * five).str();
    mid_temp.pop_back();
    mid = mid_temp;

    product = mid * abs_b;

    if ((product <= abs_this) && ((mid + one) * abs_b > abs_this)) {
      Bigint quotient = Bigint(mid.num, !(this->sign ^ b.sign));
      Bigint remainder = *this - (quotient * b);
      return make_pair(quotient, remainder);
    } else if (product > abs_this) {
      right = mid - one;
    } else {
      left = mid + one;
    }
  }
  throw runtime_error("Division Error");
}
```
Improve the Bigint::multi function.