无符号高精度

#include <bits/stdc++.h>
typedef long long ll;
const ll blen = 9;
const ll base = 1e9;
const ll pw[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
ll null;
struct bint {
	std::vector<ll> a;
	void fix() {
		while(back() == 0 && size() > 1) {
			pop_back();
		}
	}
	bint(ll x = 0) {
		a.clear();
		a.emplace_back(x % base);
		a.emplace_back(x / base);
		fix();
	}
	bint(std::string s) {
		a.clear();
		int lim = (int)s.size() - 1;
		for(int i = lim; i >= 0; i -= 9) {
			ll x = 0;
			for(int j = std::max(0, i - 8); j <= i; j++) {
				x = x * 10 + s[j] - '0';
			}
			a.emplace_back(x);
		}
	}
	int size() const {
		return a.size();
	}
	void resize(int n) {
		a.clear();
		a.resize(n);
	}
	ll back() const {
		return a.back();
	}
	void pop_back() {
		a.pop_back();
	}
	ll operator [](const int &i) const {
		return i >= 0 && i < size() ? a[i] : 0;
	}
	ll &operator [](const int &i) {
		return i >= 0 && i < size() ? a[i] : (null = 0);
	}
	void print() const {
		printf("%lld", a.back());
		for(int i = size() - 2; i >= 0; i--) {
			printf("%09lld", a[i]);
		}
	}
	friend bool operator < (const bint &x, const bint &y) {
		if(x.size() != y.size()) {
			return x.size() < y.size();
		}
		for(int i = x.size(); i >= 0; i--) {
			if(x[i] != y[i]) {
				return x[i] < y[i];
			}
		}
		return 0;
	}
	friend bool operator > (const bint &x, const bint &y) {
		if(x.size() != y.size()) {
			return x.size() > y.size();
		}
		for(int i = x.size(); i >= 0; i--) {
			if(x[i] != y[i]) {
				return x[i] > y[i];
			}
		}
		return 0;
	}
	friend bool operator == (const bint &x, const bint &y) {
		if(x.size() != y.size()) {
			return 0;
		}
		for(int i = 0; i < x.size(); i++) {
			if(x[i] != y[i]) {
				return 0;
			}
		}
		return 1;
	}
	friend bool operator != (const bint &x, const bint &y) {
		return !(x == y);
	}
	friend bool operator <= (const bint &x, const bint &y) {
		return x < y || x == y;
	}
	friend bool operator >= (const bint &x, const bint &y) {
		return x > y || x == y;
	}
	friend bint operator + (const bint &x, const bint &y) {
		bint z;
		z.resize(std::max(x.size(), y.size()) + 1);
		for(int i = 0; i < z.size() - 1; i++) {
			z[i] += x[i] + y[i];
			z[i + 1] += z[i] / base;
			z[i] %= base;
		}
		z.fix();
		return z;
	}
	friend bint operator - (const bint &x, const bint &y) {
		assert(x >= y);
		bint z;
		z.resize(std::max(x.size(), y.size()) + 1);
		for(int i = 0; i < z.size() - 1; i++) {
			z[i] += x[i] - y[i];
			if(z[i] < 0) {
				z[i] += base;
				z[i + 1]--;
			}
		}
		z.fix();
		return z;
	}
	friend bint operator * (const bint &x, const bint &y) {
		bint z;
		z.resize(x.size() + y.size() + 1);
		for(int i = 0; i < x.size(); i++) {
			for(int j = 0; j < y.size(); j++) {
				z[i + j] += x[i] * y[j];
			}
			for(int j = 0; j < x.size() + y.size(); j++) {
				z[j + 1] += z[j] / base;
				z[j] %= base;
			}
		}
		z.fix();
		return z;
	}
	friend bint operator / (bint x, const bint &y) {
		std::vector<bint> d1, d2;
		bint z, n1 = y, n2 = bint(1);
		while(n1 <= x) {
			d1.emplace_back(n1);
			d2.emplace_back(n2);
			n1 = n1 + n1;
			n2 = n2 + n2;
		}
		int lim = d1.size() - 1;
		for(int i = lim; i >= 0; i--) {
			if(x >= d1[i]) {
				x = x - d1[i];
				z = z + d2[i];
			}
		}
		return z;
	}
	friend bint operator % (const bint &x, const bint &y) {
		return x - x / y * y;
	}
	friend bint operator + (const bint &x, const ll &y) {
		return x + bint(y);
	}
	friend bint operator + (const ll &x, const bint &y) {
		return bint(x) + y;
	}
	friend bint operator + (const bint &x, const std::string &y) {
		return x + bint(y);
	}
	friend bint operator + (const std::string &x, const bint &y) {
		return bint(x) + y;
	}
	friend bint operator - (const bint &x, const ll &y) {
		return x - bint(y);
	}
	friend bint operator - (const ll &x, const bint &y) {
		return bint(x) - y;
	}
	friend bint operator - (const bint &x, const std::string &y) {
		return x - bint(y);
	}
	friend bint operator - (const std::string &x, const bint &y) {
		return bint(x) - y;
	}
	friend bint operator * (const bint &x, const ll &y) {
		return x * bint(y);
	}
	friend bint operator * (const ll &x, const bint &y) {
		return bint(x) * y;
	}
	friend bint operator * (const bint &x, const std::string &y) {
		return x * bint(y);
	}
	friend bint operator * (const std::string &x, const bint &y) {
		return bint(x) * y;
	}
	friend bint operator / (const bint &x, const ll &y) {
		return x / bint(y);
	}
	friend bint operator / (const ll &x, const bint &y) {
		return bint(x) / y;
	}
	friend bint operator / (const bint &x, const std::string &y) {
		return x / bint(y);
	}
	friend bint operator / (const std::string &x, const bint &y) {
		return bint(x) / y;
	}
	friend bint operator % (const bint &x, const ll &y) {
		return x % bint(y);
	}
	friend bint operator % (const bint &x, const std::string &y) {
		return x % bint(y);
	}
	friend bint operator % (const ll &x, const bint &y) {
		return bint(x) % y;
	}
	friend bint operator % (const std::string &x, const bint &y) {
		return bint(x) % y;
	}
	bint operator += (const bint &x) {
		*this = *this + x;
		return *this;
	}
	bint operator += (const ll &x) {
		*this = *this + x;
		return *this;
	}
	bint operator += (const std::string &x) {
		*this = *this + x;
		return *this;
	}
	bint operator -= (const bint &x) {
		*this = *this - x;
		return *this;
	}
	bint operator -= (const ll &x) {
		*this = *this - x;
		return *this;
	}
	bint operator -= (const std::string &x) {
		*this = *this - x;
		return *this;
	}
	bint operator *= (const bint &x) {
		*this = *this * x;
		return *this;
	}
	bint operator *= (const ll &x) {
		*this = *this * x;
		return *this;
	}
	bint operator *= (const std::string &x) {
		*this = *this * x;
		return *this;
	}
	bint operator /= (const bint &x) {
		*this = *this / x;
		return *this;
	}
	bint operator /= (const ll &x) {
		*this = *this / x;
		return *this;
	}
	bint operator /= (const std::string &x) {
		*this = *this / x;
		return *this;
	}
	bint operator %= (const bint &x) {
		*this = *this % x;
		return *this;
	}
	bint operator %= (const ll &x) {
		*this = *this % x;
		return *this;
	}
	bint operator %= (const std::string &x) {
		*this = *this % x;
		return *this;
	}
};