高精度

class INT {
private:
	static const int BASE = 10000;   // 万进制
	static const int BASE_DIGITS = 4; // 每4位一组
	std::vector<int> digits;         // 小端序存储（低位在前）
	bool sign;                       // true为非负，false为负
	
	// 移除前导零并处理0的符号
	void trim() {
		while (digits.size() > 1 && digits.back() == 0)
			digits.pop_back();
		if (digits.size() == 1 && digits[0] == 0)
			sign = true; // 确保0的符号为正
	}
	
	// 比较绝对值大小（忽略符号）
	int compareAbs(const INT& other) const {
		if (digits.size() != other.digits.size())
			return digits.size() < other.digits.size() ? -1 : 1;
		for (int i = digits.size() - 1; i >= 0; --i) {
			if (digits[i] != other.digits[i])
				return digits[i] < other.digits[i] ? -1 : 1;
		}
		return 0;
	}
	
public:
	// 构造函数
	INT() : digits(1, 0), sign(true) {}
	INT(long long num) {
		*this = INT(std::to_string(num));
	}
	INT(const std::string& s) {
		sign = true;
		int len = s.size();
		int start = 0;
		
		// 处理符号
		if (s[0] == '-') {
			sign = false;
			start = 1;
		} else if (s[0] == '+') {
			start = 1;
		}
		
		// 跳过前导零
		while (start < len - 1 && s[start] == '0')
			start++;
		
		// 按4位分组
		digits.clear();
		for (int i = len - 1; i >= start; i -= BASE_DIGITS) {
			int num = 0;
			for (int j = std::max(start, i - BASE_DIGITS + 1); j <= i; ++j) {
				num = num * 10 + (s[j] - '0');
			}
			digits.push_back(num);
		}
		if (digits.empty()) digits.push_back(0);
		trim();
	}
	
	// 拷贝构造函数
	INT(const INT& other) = default;
	
	// 赋值运算符
	INT& operator=(const INT& other) = default;
	
	// 转换为字符串
	std::string toString() const {
		if (digits.empty()) return "0";
		std::string res;
		if (!sign) res += '-';
		res += std::to_string(digits.back());
		
		for (int i = digits.size() - 2; i >= 0; --i) {
			std::string s = std::to_string(digits[i]);
			res += std::string(BASE_DIGITS - s.size(), '0') + s;
		}
		return res;
	}
	
	// 友元输入输出
	friend std::ostream& operator<<(std::ostream& out, const INT& num) {
		out << num.toString();
		return out;
	}
	
	friend std::istream& operator>>(std::istream& in, INT& num) {
		std::string s;
		in >> s;
		num = INT(s);
		return in;
	}
	
	// 比较运算符
	bool operator<(const INT& other) const {
		if (sign != other.sign) 
			return !sign;
		return sign ? compareAbs(other) < 0 : compareAbs(other) > 0;
	}
	
	bool operator>(const INT& other) const { return other < *this; }
	bool operator<=(const INT& other) const { return !(other < *this); }
	bool operator>=(const INT& other) const { return !(*this < other); }
	bool operator==(const INT& other) const {
		return sign == other.sign && digits == other.digits;
	}
	bool operator!=(const INT& other) const { return !(*this == other); }
	
	// 算术运算符
	INT operator-() const {
		INT res = *this;
		if (res != INT(0)) res.sign = !res.sign;
		return res;
	}
	
	INT operator+(const INT& other) const {
		if (sign == other.sign) {
			INT res;
			res.sign = sign;
			res.digits.assign(std::max(digits.size(), other.digits.size()) + 1, 0);
			for (int i = 0; i < res.digits.size() - 1; ++i) {
				int a = i < digits.size() ? digits[i] : 0;
				int b = i < other.digits.size() ? other.digits[i] : 0;
				res.digits[i] += a + b;
				if (res.digits[i] >= BASE) {
					res.digits[i] -= BASE;
					res.digits[i + 1]++;
				}
			}
			res.trim();
			return res;
		}
		return *this - (-other);
	}
	
	INT operator-(const INT& other) const {
		if (sign == other.sign) {
			if (compareAbs(other) >= 0) {
				INT res;
				res.sign = sign;
				res.digits.resize(digits.size());
				int borrow = 0;
				for (int i = 0; i < digits.size(); ++i) {
					int a = digits[i];
					int b = i < other.digits.size() ? other.digits[i] : 0;
					int temp = a - b - borrow;
					if (temp < 0) {
						temp += BASE;
						borrow = 1;
					} else {
						borrow = 0;
					}
					res.digits[i] = temp;
				}
				res.trim();
				return res;
			}
			return -(other - *this);
		}
		return *this + (-other);
	}
	
	INT operator*(const INT& other) const {
		INT res;
		res.digits.assign(digits.size() + other.digits.size(), 0);
		res.sign = (sign == other.sign);
		
		for (int i = 0; i < digits.size(); ++i) {
			int carry = 0;
			for (int j = 0; j < other.digits.size() || carry; ++j) {
				long long cur = res.digits[i + j] + 
				(long long)digits[i] * (j < other.digits.size() ? other.digits[j] : 0) + 
				carry;
				res.digits[i + j] = cur % BASE;
				carry = cur / BASE;
			}
		}
		res.trim();
		return res;
	}
	
	INT operator/(const INT& other) const {
		if (other == INT(0)) throw std::runtime_error("Division by zero");
		INT res, cur;
		res.sign = (sign == other.sign);
		res.digits.assign(digits.size(), 0);
		
		for (int i = digits.size() - 1; i >= 0; --i) {
			cur = cur * BASE + digits[i];
			int l = 0, r = BASE;
			while (l < r) {
				int mid = (l + r) / 2;
				if (other.abs() * mid <= cur) {
					l = mid + 1;
				} else {
					r = mid;
				}
			}
			res.digits[i] = r - 1;
			cur -= other.abs() * (r - 1);
		}
		res.trim();
		return res;
	}
	
	INT operator%(const INT& other) const {
		return *this - (*this / other) * other;
	}
	
	// 赋值运算符
	INT& operator+=(const INT& other) { *this = *this + other; return *this; }
	INT& operator-=(const INT& other) { *this = *this - other; return *this; }
	INT& operator*=(const INT& other) { *this = *this * other; return *this; }
	INT& operator/=(const INT& other) { *this = *this / other; return *this; }
	INT& operator%=(const INT& other) { *this = *this % other; return *this; }
	
	// 幂运算（快速幂）
	INT pow(long long exponent) const {
		if (exponent < 0) return pow(-exponent).inverse();
		INT res(1), base = *this;
		while (exponent) {
			if (exponent & 1) res = res * base;
			base = base * base;
			exponent >>= 1;
		}
		return res;
	}
	
	// 绝对值
	INT abs() const {
		INT res = *this;
		res.sign = true;
		return res;
	}
	
	// 倒数（用于负指数幂）
	INT inverse() const {
		if (*this == INT(0)) 
			throw std::runtime_error("Division by zero");
		return INT(1) / *this;
	}
	
	// 常用常量
	static INT zero() { return INT(0); }
	static INT one() { return INT(1); }
	static INT ten() { return INT(10); }
};