fork download

#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <string>
#include <utility>
 
using namespace std;
 
class BigInt;
class BitField;
 
template <class X> 
class Pool {
public:
    class Ptr {
	public:
		Ptr();
		Ptr(const Ptr& ptr);
		virtual ~Ptr();
		Ptr& operator =(const Ptr& ptr);
		X& operator *() const;
		X* operator ->() const;
		X* get() const;
	protected:
		X* x;
		unsigned int* cnt;
		void release();
	};
protected:
	struct Entry {
		X* x;
		unsigned int* cnt;
	};
	Entry* buf;
	unsigned int buf_sz;
	unsigned int cnt;
	Pool();
	virtual ~Pool();
	Entry get();
	void putBack(const Entry& ent);
	static Pool instance;
	friend Ptr;
};
 
extern bool primalityTestMillerRabin(const BigInt& p, const unsigned int& cnt = 100);
 
class BigInt {
public:
	BigInt(const int& num = 0);
	BigInt(const string& str, const unsigned int& base = 10);
	BigInt(const BigInt& num);
	BigInt operator -() const;
	BigInt operator +(const BigInt& ade) const;
	BigInt operator -(const BigInt& sub) const;
	BigInt operator *(const BigInt& mer) const;
	BigInt operator /(const BigInt& dsr) const;
	BigInt operator %(const BigInt& nrm) const;
	BigInt operator <<(const size_t& wid) const;
	BigInt operator >>(const size_t& wid) const;
	BigInt& operator =(const BigInt& num);
	BigInt& operator +=(const BigInt& ade);
	BigInt& operator -=(const BigInt& sub);
	BigInt& operator *=(const BigInt& mer);
	BigInt& operator /=(const BigInt& dsr);
	BigInt& operator %=(const BigInt& nrm);
	BigInt& operator <<=(const unsigned int& wid);
	BigInt& operator >>=(const unsigned int& wid);
	BigInt& operator ++();
	BigInt operator ++(int);
	BigInt& operator --();
	BigInt operator --(int);
	bool operator ==(const BigInt& num) const;
	bool operator <(const BigInt& num) const;
	bool operator >(const BigInt& num) const;
	bool operator !=(const BigInt& num) const;
	bool operator <=(const BigInt& num) const;
	bool operator >=(const BigInt& num) const;
	BigInt power(const BigInt& exp) const;
	BigInt power(const BigInt& exp, const BigInt& nrm) const;
	BigInt gcd(const BigInt& num) const;
	BigInt lcm(const BigInt& num) const;
	BigInt inverse(const BigInt& num) const;
	BigInt abs() const;
	bool isZero() const;
	int getSign() const;
	bool getLSBit() const;
	unsigned int getLSInt() const;
	void setInt(const int& num);
	string toString(const unsigned int& base = 10) const;
protected:
	class BFPtr : public Pool<BitField>::Ptr {
	public:
		BFPtr();
		BFPtr(const unsigned int& num);
		BFPtr(const BitField& fld);
	};
	int sign;
	BFPtr fld;
	BigInt(const int& sign, const BFPtr& fld);
	static const unsigned int INT_WID;
	static BFPtr add(const BFPtr& age, const BFPtr& ade);
	static BFPtr subtract(const BFPtr& min, const BFPtr& sub);
	static BFPtr multiply(const BFPtr& mca, const BFPtr& mer);
	static pair<BFPtr, BFPtr> divide(const BFPtr& dde, const BFPtr& dsr);
	static unsigned int charToFigure(const char& ch);
	static char figureToChar(const unsigned int& fig);
};
 
class BitField {
public:
	class IntInputStream {
	public:
		IntInputStream(const BitField* fld);
		bool isEOF() const;
		unsigned int getInt();
	protected:
		const BitField* fld;
		unsigned int end;
		unsigned int cur;
		unsigned int last;
		unsigned int low_wid;
		unsigned int high_wid;
		unsigned int low_mask;
		unsigned int high_mask;
		unsigned int rem;
		unsigned int num;
	};
	class IntOutputStream {
	public:
		IntOutputStream(BitField* fld);
		virtual ~IntOutputStream();
		void putInt(const unsigned int& num);
		void flush();
	protected:
		BitField* fld;
		unsigned int end;
		unsigned int cur;
		unsigned int low_wid;
		unsigned int high_wid;
		unsigned int low_mask;
		unsigned int high_mask;
		unsigned int high;
	};
	BitField();
	BitField(const unsigned int& num);
	BitField(const BitField& fld);
	virtual ~BitField();
	BitField& operator =(const BitField& fld);
	unsigned int getWidth() const;
	bool isEmpty() const;
	bool isZero() const;
	bool getBit(const unsigned int& pos) const;
	bool getLSBit() const;
	bool getMSBit() const;
	unsigned int getLSInt() const;
	void setBit(const unsigned int& pos, const bool& bit);
	void pushMSBit(const bool& bit);
	void pushLSBit(const bool& bit);
	void setInt(const unsigned int& num);
	void shift(const int& wid);
	void trim();
	void clear();
	int compare(const BitField& fld) const;
	string toString() const;
protected:
	unsigned char* buf;
	unsigned int buf_sz;
	int beg;
	unsigned int wid;
	bool extendIfNecessary(const int& wid);
	friend IntInputStream;
	friend IntOutputStream;
};
 
#define ASSERT(pred) assert(#pred, pred);
 
extern void assert(const char* pred_str, const bool& pred);
 
template <class X> 
Pool<X>::Ptr::Ptr() {
	Entry ent = Pool<X>::instance.get();
	this->x = ent.x;
	this->cnt = ent.cnt;
	if (this->cnt) (*this->cnt)++;
}
 
template <class X> 
Pool<X>::Ptr::Ptr(const Ptr& ptr) : x(ptr.x), cnt(ptr.cnt) {
	if (this->cnt) (*this->cnt)++;
}
 
template <class X> 
Pool<X>::Ptr::~Ptr() {
	release();
}
 
template <class X> 
typename Pool<X>::Ptr& Pool<X>::Ptr::operator =(const Ptr& ptr) {
	release();
	this->x = ptr.x;
	this->cnt = ptr.cnt;
	if (this->cnt) (*this->cnt)++;
	return *this;
}
 
template <class X> 
X& Pool<X>::Ptr::operator *() const {
	return *this->x;
}
 
template <class X> 
X* Pool<X>::Ptr::operator ->() const {
	return this->x;
}
 
template <class X> 
X* Pool<X>::Ptr::get() const {
	return this->x;
}
 
template <class X> 
void Pool<X>::Ptr::release() {
	if (this->cnt && --*this->cnt == 0) {
		Entry ent;
		ent.x = this->x;
		ent.cnt = this->cnt;
		Pool<X>::instance.putBack(ent);
	}
}
 
template <class X> 
Pool<X>::Pool() : buf(nullptr), buf_sz(0), cnt(0) {}
 
template <class X> 
Pool<X>::~Pool() {
	for (int i = 0; i < this->cnt; i++) {
		delete this->buf[i].x;
		delete this->buf[i].cnt;
	}
	delete[] this->buf;
}
 
template <class X> 
typename Pool<X>::Entry Pool<X>::get() {
	if (this->cnt == 0) {
		Entry ent;
		ent.x = new X;
		ent.cnt = new unsigned int(0);
		putBack(ent);
	}
	return this->buf[--this->cnt];
}
 
template <class X> 
void Pool<X>::putBack(const Entry& ent) {
	unsigned int need_sz = this->cnt + 1;
	if (need_sz > this->buf_sz) {
		unsigned int new_buf_sz = need_sz * 2;
		Entry* new_buf = new Entry[new_buf_sz];
		if (this->buf_sz != 0) {
			memcpy(new_buf, this->buf, sizeof(Entry) * this->cnt);
			delete[] this->buf;
		}
		this->buf = new_buf;
		this->buf_sz = new_buf_sz;
	}
	this->buf[this->cnt++] = ent;
}
 
template <class X> 
Pool<X> Pool<X>::instance;
 
bool primalityTestMillerRabin(const BigInt& p, const unsigned int& cnt) {
	bool res = true;
	if (p == 1) res = false;
	else if (p == 2) res = true;
	else if (p.getLSBit() == false) res = false;
	else {
		BigInt o = p - 1;
		BigInt q = o;
		BigInt k(1);
		while (q.getLSBit() == false) {
			q >>= 1;
			k++;
		}
		BigInt a(2);
		BigInt gap((o - 2) / cnt);
		if (gap.isZero()) gap = 1;
		for (; a < p; a += gap) {
			BigInt b = a.power(q, p);
			if (b != 1 && b != o) {
				BigInt i(1);
				for (; i < k; i++) {
					b = (b * b) % p;
					if (b == o) break;
				}
				if (i == k) {
					res = false;
					break;
				}
			}
		}
	}
	return res;
}
 
BigInt::BFPtr::BFPtr() {
	this->x->clear();
}
 
BigInt::BFPtr::BFPtr(const unsigned int& num) {
	this->x->setInt(num);
}
 
BigInt::BFPtr::BFPtr(const BitField& fld) {
	*this->x = fld;
}
 
BigInt::BigInt(const int& num) {
	this->sign = num >= 0 ? 1 : -1;
	this->fld->setInt(this->sign * num);
}
 
BigInt::BigInt(const string& str, const unsigned int& base) {
	this->sign = 1;
	this->fld->setInt(0);
	BFPtr base_fld(base);
	string::const_iterator iter = str.begin();
	if (*iter == '-') {
		this->sign = -1;
		iter++;
	}
	for (; iter != str.end(); iter++) {
		if (iter != str.begin()) {
			this->fld = multiply(this->fld, base_fld);
		}
		unsigned int fig = charToFigure(*iter);
		if (fig >= base) throw string("値が範囲を逸脱している。");
		BFPtr ade(fig);
		this->fld = add(this->fld, ade);
	}
	if (this->fld->isZero()) this->sign = 1;
}
 
BigInt::BigInt(const BigInt& num) {
	this->sign = num.fld->isZero() ? 1 : num.sign;
	*this->fld = *num.fld;
}
 
BigInt BigInt::operator -() const {
	return BigInt(-this->sign, BFPtr(*this->fld));
}
 
BigInt BigInt::operator +(const BigInt& ade) const {
	if (this->sign == ade.sign) 
		return BigInt(this->sign, add(this->fld, ade.fld));
	else {
		int sign;
		BFPtr gre_fld, less_fld;
		if (this->fld->compare(*ade.fld) >= 0) {
			sign = this->sign;
			gre_fld = this->fld;
			less_fld = ade.fld;
		}
		else {
			sign = ade.sign;
			gre_fld = ade.fld;
			less_fld = this->fld;
		}
		return BigInt(sign, subtract(gre_fld, less_fld));
	}
}
 
BigInt BigInt::operator -(const BigInt& sub) const {
	return operator +(-sub);
}
 
BigInt BigInt::operator *(const BigInt& mer) const {
	return BigInt(this->sign * mer.sign, multiply(this->fld, mer.fld));
}
 
BigInt BigInt::operator /(const BigInt& dsr) const {
	return BigInt(this->sign * dsr.sign, divide(this->fld, dsr.fld).first);
}
 
BigInt BigInt::operator %(const BigInt& nrm) const {
	return BigInt(this->sign, divide(this->fld, nrm.fld).second);
}
 
BigInt BigInt::operator <<(const unsigned int& wid) const {
	BFPtr fld(*this->fld);
	fld->shift(-wid);
	return BigInt(this->sign, fld);
}
 
BigInt BigInt::operator >>(const unsigned int& wid) const {
	BFPtr fld(*this->fld);
	fld->shift(wid);
	return BigInt(this->sign, fld);
}
 
BigInt& BigInt::operator =(const BigInt& num) {
	if (&num != this) {
		this->sign = num.fld->isZero() ? 1 : num.sign;
		*this->fld = *num.fld;
	}
	return *this;
}
 
BigInt& BigInt::operator +=(const BigInt& add) {
	return *this = *this + add;
}
 
BigInt& BigInt::operator -=(const BigInt& sub) {
	return *this = *this - sub;
}
 
BigInt& BigInt::operator *=(const BigInt& mer) {
	return *this = *this * mer;
}
 
BigInt& BigInt::operator /=(const BigInt& dsr) {
	return *this = *this / dsr;
}
 
BigInt& BigInt::operator %=(const BigInt& nrm) {
	return *this = *this % nrm;
}
 
BigInt& BigInt::operator <<=(const size_t& wid) {
	return *this = *this << wid;
}
 
BigInt& BigInt::operator >>=(const size_t& wid) {
	return *this = *this >> wid;
}
 
BigInt& BigInt::operator ++() {
	return *this += 1;
}
 
BigInt BigInt::operator ++(int) {
	BigInt res = *this;
	*this += 1;
	return res;
}
 
BigInt& BigInt::operator --() {
	return *this -= 1;
}
 
BigInt BigInt::operator --(int) {
	BigInt res = *this;
	*this -= 1;
	return res;
}
 
bool BigInt::operator ==(const BigInt& num) const {
	return this->sign == num.sign && this->fld->compare(*num.fld) == 0;
}
 
bool BigInt::operator <(const BigInt& num) const {
	int cmp_res = this->fld->compare(*num.fld);
	return (this->sign >= 0 && num.sign >= 0 && cmp_res < 0) || 
		(this->sign < 0 && num.sign >= 0) || 
		(this->sign < 0 && num.sign < 0 && cmp_res > 0);
}
 
bool BigInt::operator >(const BigInt& num) const {
	int cmp_res = this->fld->compare(*num.fld);
	return (this->sign >= 0 && num.sign >= 0 && cmp_res > 0) || 
		(this->sign >= 0 && num.sign < 0) || 
		(this->sign < 0 && num.sign < 0 && cmp_res < 0);
}
 
bool BigInt::operator !=(const BigInt& num) const {
	return !operator ==(num);
}
 
bool BigInt::operator <=(const BigInt& num) const {
	return !operator >(num);
}
 
bool BigInt::operator >=(const BigInt& num) const {
	return !operator <(num);
}
 
BigInt BigInt::power(const BigInt& exp) const {
	if (isZero()) return BigInt(0);
	if (exp.isZero()) return BigInt(1);
	if (exp < 0) return BigInt(1) / power(-exp);
	BigInt res(1);
	BigInt coef = *this;
	for (BigInt exp2 = exp;;) {
		if (exp2.getLSBit()) {
			res *= coef;
		}
		exp2 >>= 1;
		if (exp2.isZero()) break;
		coef *= coef;
	}
	return res;
}
 
BigInt BigInt::power(const BigInt& exp, const BigInt& nrm) const {
	if (isZero()) return BigInt(0);
	if (exp.isZero()) return BigInt(1);
	if (exp < 0) return (BigInt(1) / power(-exp)) % nrm;
	BigInt res(1);
	BigInt coef = *this % nrm;
	for (BigInt exp2 = exp;;) {
		if (exp2.getLSBit()) {
			res = (res * coef) % nrm;
		}
		exp2 >>= 1;
		if (exp2.isZero()) break;
		coef = (coef * coef) % nrm;
	}
	return res;
}
 
BigInt BigInt::gcd(const BigInt& num) const {
	BigInt a(this->abs()), b(num.abs()), r;
	if (a < b) swap(a, b);
	for (;;) {
		r = a % b;
		if (r == 0) break;
		a = b;
		b = r;
	};
	if (b.sign != this->sign) b = -b;
	return b;
}
 
BigInt BigInt::lcm(const BigInt& num) const {
	return *this * num / gcd(num);
}
 
BigInt BigInt::inverse(const BigInt& nrm) const {
	BigInt a(this->abs()), b(nrm.abs()), r, q, c, d(1), e(0);
	if (a < b) {
		swap(a, b);
		swap(d, e);
	}
	for (;;) {
		q = a / b;
		r = a % b;
		if (r == 0) break;
		c = d - e * q;
		d = e;
		e = c;
		a = b;
		b = r;
	};
	if (c.sign != nrm.sign) c += nrm;
	return c;
}
 
BigInt BigInt::abs() const {
	return BigInt(1, BFPtr(*this->fld));
}
 
bool BigInt::isZero() const {
	return this->fld->isZero();
}
 
int BigInt::getSign() const {
	return this->sign;
}
 
bool BigInt::getLSBit() const {
	return this->fld->getLSBit();
}
 
unsigned int BigInt::getLSInt() const {
	return this->fld->getLSInt();
}
 
void BigInt::setInt(const int& num) {
	this->sign = num >= 0 ? 1 : -1;
	this->fld->setInt(this->sign * num);
}
 
string BigInt::toString(const unsigned int& base) const {
	string res = "";
	pair<BFPtr, BFPtr> quo_rem(BFPtr(*this->fld), BFPtr());
	BFPtr base_fld;
	base_fld->setInt(base);
	while (!quo_rem.first->isZero()) {
		quo_rem = divide(quo_rem.first, base_fld);
		res += figureToChar(quo_rem.second->getLSInt());
	}
	if (res.empty()) res += '0';
	if (this->sign < 0) res += '-';
	reverse(res.begin(), res.end());
	size_t pos = 0;
	for (; pos < res.length() - 1; pos++) if (res[pos] != '0') break;
	return res.substr(pos, res.length() - pos);
}
 
BigInt::BigInt(const int& sign, const BFPtr& fld) {
	this->sign = fld->isZero() ? 1 : sign;
	this->fld = fld;
}
 
const unsigned int BigInt::INT_WID = sizeof(unsigned int) << 3;
 
BigInt::BFPtr BigInt::add(const BFPtr& age, const BFPtr& ade) {
	BFPtr sum;
	BitField::IntOutputStream sum_out(sum.get());
	BitField::IntInputStream age_in(age.get());
	BitField::IntInputStream ade_in(ade.get());
	bool carry = false;
	while (!age_in.isEOF() || !ade_in.isEOF()) {
		unsigned int age_num = !age_in.isEOF() ? age_in.getInt() : 0;
		unsigned int ade_num = !ade_in.isEOF() ? ade_in.getInt() : 0;
		unsigned int sum_num = (age_num & ~(1 << (INT_WID - 1))) + (ade_num & ~(1 << (INT_WID - 1))) + (carry ? 1 : 0);
		int ms_num = (age_num >> (INT_WID - 1)) + (ade_num >> (INT_WID - 1)) + (sum_num >> (INT_WID - 1));
		carry = ms_num > 1;
		if (carry) ms_num -= 2;
		sum_num = (sum_num & ~(1 << (INT_WID - 1))) | (ms_num << (INT_WID - 1));
		sum_out.putInt(sum_num);
	}
	sum_out.flush();
	if (carry) sum->pushMSBit(true);
	if (sum->isEmpty()) sum->pushMSBit(false);
	sum->trim();
	return sum;
}
 
BigInt::BFPtr BigInt::subtract(const BFPtr& min, const BFPtr& sub) {
	BFPtr dif;
	BitField::IntOutputStream dif_out(dif.get());
	BitField::IntInputStream min_in(min.get());
	BitField::IntInputStream sub_in(sub.get());
	bool borrow = false;
	while (!min_in.isEOF() || !sub_in.isEOF()) {
		unsigned int min_num = !min_in.isEOF() ? min_in.getInt() : 0;
		unsigned int sub_num = !sub_in.isEOF() ? sub_in.getInt() : 0;
		unsigned int dif_num = (min_num | (1 << (INT_WID - 1))) - (sub_num & ~(1 << (INT_WID - 1))) - (borrow ? 1 : 0);
		int ms_num = (min_num >> (INT_WID - 1)) - (sub_num >> (INT_WID - 1)) - (1 - (dif_num >> (INT_WID - 1)));
		borrow = ms_num < 0;
		if (borrow) ms_num += 2;
		dif_num = (dif_num & ~(1 << (INT_WID - 1))) | (ms_num << (INT_WID - 1));
		dif_out.putInt(dif_num);
	}
	dif_out.flush();
	if (borrow) throw string("被減数が減数より小さい。");
	if (dif->isEmpty()) dif->pushMSBit(false);
	dif->trim();
	return dif;
}
 
BigInt::BFPtr BigInt::multiply(const BFPtr& mca, const BFPtr& mer) {
	BFPtr pro(0);
	BFPtr wrk(*mca);
	for (unsigned int mer_pos = 0; mer_pos < mer->getWidth(); mer_pos++) {
		if (mer->getBit(mer_pos) == true) pro = add(pro, wrk);
		wrk->shift(-1);
	}
	return pro;
}
 
pair<BigInt::BFPtr, BigInt::BFPtr> BigInt::divide(const BFPtr& dde, const BFPtr& dsr) {
	if (dsr->isZero()) throw string("除数がゼロ。");
	pair<BFPtr, BFPtr> quo_rem;
	for (unsigned int dde_next_pos = dde->getWidth(); dde_next_pos > 0; dde_next_pos--) {
		unsigned int dde_pos = dde_next_pos - 1;
		quo_rem.second->pushLSBit(dde->getBit(dde_pos));
		if (quo_rem.second->compare(*dsr) >= 0) {
			quo_rem.first->pushLSBit(true);
			quo_rem.second = subtract(quo_rem.second, dsr);
		}
		else quo_rem.first->pushLSBit(false);
	}
	if (quo_rem.first->isEmpty()) quo_rem.first->pushMSBit(false);
	if (quo_rem.second->isEmpty()) quo_rem.second->pushMSBit(false);
	return quo_rem;
}
 
unsigned int BigInt::charToFigure(const char& ch) {
	unsigned int res;
	if (ch >= '0' && ch <= '9') res = ch - '0';
	else if (ch >= 'A' && ch <= 'Z') res = 10 + ch - 'A';
	else if (ch >= 'a' && ch <= 'z') res = 10 + ch - 'a';
	else throw string("文字が数ではない。");
	return res;
}
 
char BigInt::figureToChar(const unsigned int& fig) {
	char res;
	if (fig >= 0 && fig <= 9) res = '0' + fig;
	else if (fig >= 10 && fig <= 36) res = 'A' + (fig - 10);
	else throw string("値が範囲を逸脱している。");
	return res;
}
 
BitField::IntInputStream::IntInputStream(const BitField* fld) {
	this->fld = fld;
	this->end = fld->buf_sz / sizeof(unsigned int);
	this->cur = (this->fld->beg >> 3) / sizeof(unsigned int);
	unsigned int fld_end = this->fld->beg + this->fld->wid;
	unsigned int buf_wid = this->fld->buf_sz << 3;
	unsigned int act_fld_end;
	if (fld_end <= buf_wid) act_fld_end = fld_end;
	else act_fld_end = fld_end - buf_wid;
	this->last = ((act_fld_end - 1) >> 3) / sizeof(unsigned int);
	this->high_wid = this->fld->beg & ((sizeof(unsigned int) << 3) - 1);
	this->low_wid = (sizeof(unsigned int) << 3) - this->high_wid;
	this->high_mask = (1 << this->high_wid) - 1;
	this->low_mask = ~this->high_mask;
	this->rem = this->fld->wid;
	if (this->fld->wid != 0) this->num = ((unsigned int*)this->fld->buf)[this->cur];
}
 
bool BitField::IntInputStream::isEOF() const {
	return this->rem == 0;
}
 
unsigned int BitField::IntInputStream::getInt() {
	unsigned int res = 0;
	res |= (this->num & this->low_mask) >> this->high_wid;
	if (this->rem >= this->low_wid) {
		this->rem -= this->low_wid;
		if (this->rem != 0) {
			this->cur++;
			if (this->cur == this->end) this->cur = 0;
			this->num = ((unsigned int*)this->fld->buf)[this->cur];
			if (this->high_wid != 0) {
				res |= (this->num & this->high_mask) << this->low_wid;
				if (this->rem >= this->high_wid) 
					this->rem -= this->high_wid;
				else {
					res &= (1 << (this->low_wid + this->rem)) - 1;
					this->rem = 0;
				}
			}
		}
	}
	else {
		res &= (1 << this->rem) - 1;
		this->rem = 0;
	}
	return res;
}
 
BitField::IntOutputStream::IntOutputStream(BitField* fld) {
	this->fld = fld;
	this->end = this->fld->buf_sz / sizeof(unsigned int);
	unsigned int fld_end = this->fld->beg + this->fld->wid;
	unsigned int buf_wid = this->fld->buf_sz << 3;
	unsigned int act_fld_end;
	if (fld_end <= buf_wid) act_fld_end = fld_end;
	else act_fld_end = fld_end - buf_wid;
	this->cur = (act_fld_end >> 3) / sizeof(unsigned int);
	this->high_wid = act_fld_end & ((sizeof(unsigned int) << 3) - 1);
	this->low_wid = (sizeof(unsigned int) << 3) - this->high_wid;
	this->high_mask = (1 << this->high_wid) - 1;
	this->low_mask = ~this->high_mask;
	if (this->fld->wid != 0) 
		this->high = ((unsigned int*)this->fld->buf)[this->cur] & this->high_mask;
	else this->high = 0;
}
 
BitField::IntOutputStream::~IntOutputStream() {
	flush();
}
 
void BitField::IntOutputStream::putInt(const unsigned int& num) {
	this->fld->extendIfNecessary(sizeof(unsigned int) << 3);
	((unsigned int*)this->fld->buf)[this->cur] = this->high | ((num << this->high_wid) & this->low_mask);
	this->cur++;
	if (this->high_wid != 0) 
		this->high = num >> this->low_wid;
}
 
void BitField::IntOutputStream::flush() {
	if (this->high_wid != 0) 
		((unsigned int*)this->fld->buf)[this->cur] = this->high | (((unsigned int*)this->fld->buf)[this->cur] & this->low_mask);
}
 
BitField::BitField() : buf(nullptr), buf_sz(0), beg(0), wid(0) {}
 
BitField::BitField(const unsigned int& num) : buf(nullptr), buf_sz(0), beg(0), wid(0) {
	extendIfNecessary(sizeof(unsigned int) << 3);
	*(unsigned int*)this->buf = num;
	trim();
}
 
BitField::BitField(const BitField& fld) : buf(nullptr), buf_sz(0), beg(0), wid(0) {
	if (fld.wid != 0) {
		this->buf_sz = fld.buf_sz;
		this->buf = new unsigned char[this->buf_sz];
		memcpy(this->buf, fld.buf, fld.buf_sz);
		this->beg = fld.beg;
		this->wid = fld.wid;
	}
}
 
BitField::~BitField() {
	if (this->buf) delete[] this->buf;
}
 
BitField& BitField::operator =(const BitField& fld) {
	if (&fld != this) {
		this->wid = 0;
		if (fld.wid != 0) {
			this->buf_sz = fld.buf_sz;
			this->buf = new unsigned char[this->buf_sz];
			memcpy(this->buf, fld.buf, fld.buf_sz);
			this->beg = fld.beg;
			this->wid = fld.wid;
		}
	}
	return *this;
}
 
unsigned int BitField::getWidth() const {
	return this->wid;
}
 
bool BitField::isEmpty() const {
	return this->wid == 0;
}
 
bool BitField::isZero() const {
	bool res = true;
	for (unsigned int pos = 0; pos < this->wid; pos++) {
		if (getBit(pos) == true) {
			res = false;
			break;
		}
	}
	return res;
}
 
bool BitField::getBit(const unsigned int& pos) const {
	unsigned int abs_pos = this->beg + pos;
	unsigned int buf_wid = this->buf_sz << 3;
	if (abs_pos >= buf_wid) abs_pos -= buf_wid;
	return ((this->buf[abs_pos >> 3] >> (abs_pos & 0x7)) & 1) == 1;
}
 
bool BitField::getLSBit() const {
	return getBit(0);
}
 
bool BitField::getMSBit() const {
	return getBit(this->wid - 1);
}
 
unsigned int BitField::getLSInt() const {
	unsigned int res = 0;
	unsigned int int_wid = sizeof(unsigned int) << 3;
	for (unsigned int pos = 0; pos < int_wid && pos < this->wid; pos++) 
		res |= (getBit(pos) == true ? 1 : 0) << pos;
	return res;
}
 
void BitField::setBit(const unsigned int& pos, const bool& bit) {
	unsigned int abs_pos = this->beg + pos;
	unsigned int buf_wid = this->buf_sz << 3;
	if (abs_pos >= buf_wid) abs_pos -= buf_wid;
	if (bit) this->buf[abs_pos >> 3] |= 1 << (abs_pos & 0x7);
	else this->buf[abs_pos >> 3] &= ~(1 << (abs_pos & 0x7));
}
 
void BitField::pushMSBit(const bool& bit) {
	extendIfNecessary(1);
	setBit(this->wid - 1, bit);
}
 
void BitField::pushLSBit(const bool& bit) {
	extendIfNecessary(-1);
	setBit(0, bit);
}
 
void BitField::setInt(const unsigned int& num) {
	clear();
	extendIfNecessary(sizeof(unsigned int) << 3);
	*(unsigned int*)this->buf = num;
	trim();
}
 
void BitField::shift(const int& wid) {
	if (wid < 0) {
		extendIfNecessary(wid);
		for (unsigned int pos = 0; pos < -wid; pos++) 
			setBit(pos, false);
	}
	else {
		this->beg += wid;
		unsigned int buf_wid = this->buf_sz << 3;
		if (this->beg >= buf_wid) this->beg -= buf_wid;
		this->wid -= wid;
	}
}
 
void BitField::trim() {
	while (this->wid != 0 && getMSBit() == false) this->wid--;
}
 
void BitField::clear() {
	this->beg = 0;
	this->wid = 0;
}
 
int BitField::compare(const BitField& fld) const {
	int res = 0;
	for (unsigned int next_pos = this->wid < fld.wid ? fld.wid : this->wid; next_pos > 0; next_pos--) {
		unsigned int pos = next_pos - 1;
		bool bit1 = pos < this->wid ? getBit(pos) : false;
		bool bit2 = pos < fld.wid ? fld.getBit(pos) : false;
		if (bit1 == false && bit2 == true) {
			res = -1;
			break;
		}
		else if (bit1 == true && bit2 == false) {
			res = 1;
			break;
		}
	}
	return res;
}
 
string BitField::toString() const {
	string res = "";
	for (unsigned int pos = 0; pos < this->wid; pos++) 
		res += getBit(pos) == true ? '1' : '0';
	return res;
}
 
bool BitField::extendIfNecessary(const int& wid) {
	bool res = false;
	unsigned int abs_wid = wid < 0 ? -wid : wid;
	unsigned int need_sz = (this->wid + abs_wid + 7) >> 3;
	if (need_sz > this->buf_sz) {
		unsigned int new_buf_sz = need_sz << 1;
		new_buf_sz = ((new_buf_sz + 3) >> 2) << 2;
		unsigned char* new_buf = new unsigned char[new_buf_sz];
		unsigned int new_beg = 0;
		if (this->wid != 0) {
			unsigned int fld_beg = this->beg >> 3;
			unsigned int fld_end = (this->beg + this->wid + 7) >> 3;
			if (fld_end <= this->buf_sz) {
				unsigned int fld_sz = fld_end - fld_beg;
				memcpy(new_buf + fld_beg, this->buf + fld_beg, fld_sz);
				new_beg = this->beg;
			}
			else {
				unsigned int low_sz = this->buf_sz - fld_beg;
				unsigned int new_low_beg = new_buf_sz - low_sz;
				memcpy(new_buf + new_low_beg, this->buf + fld_beg, low_sz);
				unsigned int high_sz = fld_end - this->buf_sz;
				memcpy(new_buf, this->buf, high_sz);
				unsigned int buf_wid = this->buf_sz << 3;
				unsigned int low_wid = buf_wid - this->beg;
				unsigned int new_buf_wid = new_buf_sz << 3;
				new_beg = new_buf_wid - low_wid;
			}
			delete[] this->buf;
			res = true;
		}
		this->buf_sz = new_buf_sz;
		this->buf = new_buf;
		this->beg = new_beg;
	}
	if (wid < 0) {
		this->beg += wid;
		int buf_wid = this->buf_sz << 3;
		if (this->beg < 0) this->beg += buf_wid;
	}
	this->wid += abs_wid;
	return res;
}
 
void assert(const char* pred_str, const bool& pred) {
	if (pred) {
		cout << "アサート成功: " << pred_str << endl;
	}
	else {
		cerr << "アサート失敗: " << pred_str << endl;
		exit(1);
	}
}
 
int main() {
	try {
		clock_t begin = clock();
 
		ASSERT(BigInt(0).getSign() == 1)
		ASSERT(BigInt(0).getLSInt() == 0)
		ASSERT(BigInt(1).getSign() == 1)
		ASSERT(BigInt(1).getLSInt() == 1)
		ASSERT(BigInt(123).getSign() == 1)
		ASSERT(BigInt(123).getLSInt() == 123)
		ASSERT(BigInt(1234567890).getSign() == 1)
		ASSERT(BigInt(1234567890).getLSInt() == 1234567890)
		ASSERT(BigInt(-0).getSign() == 1)
		ASSERT(BigInt(-0).getLSInt() == 0)
		ASSERT(BigInt(-1).getSign() == -1)
		ASSERT(BigInt(-1).getLSInt() == 1)
		ASSERT(BigInt(-123).getSign() == -1)
		ASSERT(BigInt(-123).getLSInt() == 123)
		ASSERT(BigInt(-1234567890).getSign() == -1)
		ASSERT(BigInt(-1234567890).getLSInt() == 1234567890)
 
		ASSERT(BigInt("0").toString() == "0")
		ASSERT(BigInt("-0").toString() == "0")
		ASSERT(BigInt("1").toString() == "1")
		ASSERT(BigInt("-1").toString() == "-1")
		ASSERT(BigInt("341").toString() == "341")
		ASSERT(BigInt("-341").toString() == "-341")
		ASSERT(BigInt("123342").toString() == "123342")
		ASSERT(BigInt("-123342").toString() == "-123342")
		ASSERT(BigInt("9825724079207842808027478042").toString() == "9825724079207842808027478042")
		ASSERT(BigInt("-9825724079207842808027478042").toString() == "-9825724079207842808027478042")
 
		ASSERT(-BigInt("0") == BigInt("0"))
		ASSERT(-BigInt("1") == BigInt("-1"))
		ASSERT(-BigInt("123") == BigInt("-123"))
		ASSERT(-BigInt("98765432109876543210") == BigInt("-98765432109876543210"))
		ASSERT(BigInt("107777896329") + BigInt("744936075025") == BigInt("1540169976256") - BigInt("687456004902"))
		ASSERT(BigInt("51") + BigInt("65") == BigInt("116"))
		ASSERT(BigInt("51") + BigInt("-65") == BigInt("-14"))
		ASSERT(BigInt("-51") + BigInt("65") == BigInt("14"))
		ASSERT(BigInt("-51") + BigInt("-65") == BigInt("-116"))
		ASSERT(BigInt("51") - BigInt("65") == BigInt("-14"))
		ASSERT(BigInt("51") - BigInt("-65") == BigInt("116"))
		ASSERT(BigInt("-51") - BigInt("65") == BigInt("-116"))
		ASSERT(BigInt("-51") - BigInt("-65") == BigInt("14"))
		ASSERT(BigInt("2") * BigInt("11111") == BigInt("66666") / BigInt("3"))
		ASSERT(BigInt("37") * BigInt("10") == BigInt("370"))
		ASSERT(BigInt("37") * BigInt("-10") == BigInt("-370"))
		ASSERT(BigInt("-37") * BigInt("10") == BigInt("-370"))
		ASSERT(BigInt("-37") * BigInt("-10") == BigInt("370"))
		ASSERT(BigInt("37") / BigInt("10") == BigInt("3"))
		ASSERT(BigInt("37") / BigInt("-10") == BigInt("-3"))
		ASSERT(BigInt("-37") / BigInt("10") == BigInt("-3"))
		ASSERT(BigInt("-37") / BigInt("-10") == BigInt("3"))
		ASSERT(BigInt("55555555123") % BigInt("10000") == BigInt("5123"))
		ASSERT(BigInt("37") % BigInt("10") == BigInt("7"))
		ASSERT(BigInt("37") % BigInt("-10") == BigInt("7"))
		ASSERT(BigInt("-37") % BigInt("10") == BigInt("-7"))
		ASSERT(BigInt("-37") % BigInt("-10") == BigInt("-7"))
		ASSERT(BigInt("12345678901234567890") == BigInt("12345678901234567890"))
		ASSERT(BigInt("999999999") < BigInt("1000000000"))
		ASSERT(BigInt("1000000001") > BigInt("1000000000"))
		ASSERT(BigInt("789AbCdEf", 16) == BigInt("32374509039"))
		ASSERT(BigInt("789AbCdEf", 16) - BigInt("32374509000") == BigInt("39"))
		ASSERT(BigInt("1A", 16) << 1 == BigInt("34", 16))
		ASSERT(BigInt("1A", 16) >> 2 == BigInt("6", 16))
 
		{
			BigInt a, b;
			a.setInt(12);
			a = a;
			ASSERT(a == BigInt(12))
			a.setInt(34);
			a = a;
			ASSERT(a == BigInt(34))
			b = a;
			ASSERT(a == BigInt(34))
			ASSERT(b == BigInt(34))
			a.setInt(56);
			ASSERT(a == BigInt(56))
			ASSERT(b == BigInt(34))
			b.setInt(78);
			ASSERT(a == BigInt(56))
			ASSERT(b == BigInt(78))
		}
 
		ASSERT(BigInt("0").power(BigInt("0")) == BigInt("0"))
		ASSERT(BigInt("1").power(BigInt("0")) == BigInt("1"))
		ASSERT(BigInt("2").power(BigInt("0")) == BigInt("1"))
		ASSERT(BigInt("5222256474787565634234256467876").power(BigInt("0")) == BigInt("1"))
		ASSERT(BigInt("0").power(BigInt("1")) == BigInt("0"))
		ASSERT(BigInt("1").power(BigInt("1")) == BigInt("1"))
		ASSERT(BigInt("2").power(BigInt("1")) == BigInt("2"))
		ASSERT(BigInt("5222256474787565634234256467876").power(BigInt("1")) == BigInt("5222256474787565634234256467876"))
		ASSERT(BigInt("0").power(BigInt("4")) == BigInt("0"))
		ASSERT(BigInt("0").power(BigInt("4"), BigInt("10")) == BigInt("0"))
		ASSERT(BigInt("0").power(BigInt("4"), BigInt("-10")) == BigInt("0"))
		ASSERT(BigInt("1").power(BigInt("4")) == BigInt("1"))
		ASSERT(BigInt("1").power(BigInt("4"), BigInt("10")) == BigInt("1"))
		ASSERT(BigInt("1").power(BigInt("4"), BigInt("-10")) == BigInt("1"))
		ASSERT(BigInt("2").power(BigInt("4")) == BigInt("16"))
		ASSERT(BigInt("2").power(BigInt("4"), BigInt("10")) == BigInt("6"))
		ASSERT(BigInt("2").power(BigInt("4"), BigInt("-10")) == BigInt("6"))
		ASSERT(BigInt("-0").power(BigInt("4")) == BigInt("0"))
		ASSERT(BigInt("-0").power(BigInt("4"), BigInt("10")) == BigInt("0"))
		ASSERT(BigInt("-0").power(BigInt("4"), BigInt("-10")) == BigInt("0"))
		ASSERT(BigInt("-1").power(BigInt("4")) == BigInt("1"))
		ASSERT(BigInt("-1").power(BigInt("4"), BigInt("10")) == BigInt("1"))
		ASSERT(BigInt("-1").power(BigInt("4"), BigInt("-10")) == BigInt("1"))
		ASSERT(BigInt("-2").power(BigInt("4")) == BigInt("16"))
		ASSERT(BigInt("-2").power(BigInt("4"), BigInt("10")) == BigInt("6"))
		ASSERT(BigInt("-2").power(BigInt("4"), BigInt("-10")) == BigInt("6"))
		ASSERT(BigInt("-3").power(BigInt("3")) == BigInt("-27"))
		ASSERT(BigInt("-3").power(BigInt("3"), BigInt("10")) == BigInt("-7"))
		ASSERT(BigInt("-3").power(BigInt("3"), BigInt("-10")) == BigInt("-7"))
		ASSERT(BigInt("0").power(BigInt("-5")) == BigInt("0"))
		ASSERT(BigInt("1").power(BigInt("-5")) == BigInt("1"))
		ASSERT(BigInt("2").power(BigInt("-5")) == BigInt("0"))
		ASSERT(BigInt("0").power(BigInt("-5"), BigInt("10")) == BigInt("0"))
		ASSERT(BigInt("1").power(BigInt("-5"), BigInt("10")) == BigInt("1"))
		ASSERT(BigInt("2").power(BigInt("-5"), BigInt("10")) == BigInt("0"))
		ASSERT(BigInt("0").power(BigInt("-5"), BigInt("-10")) == BigInt("0"))
		ASSERT(BigInt("1").power(BigInt("-5"), BigInt("-10")) == BigInt("1"))
		ASSERT(BigInt("2").power(BigInt("-5"), BigInt("-10")) == BigInt("0"))
		ASSERT(BigInt("12").power(BigInt("34")) == BigInt("4922235242952026704037113243122008064"))
		ASSERT(BigInt("12").power(BigInt("34"), BigInt("100")) == BigInt("64"))
		ASSERT(BigInt("2").power(BigInt("4099"), BigInt("100")) == BigInt("88"))
 
		ASSERT(primalityTestMillerRabin(BigInt("0")) == false)
		ASSERT(primalityTestMillerRabin(BigInt("1")) == false)
		ASSERT(primalityTestMillerRabin(BigInt("2")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("3")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("4")) == false)
		ASSERT(primalityTestMillerRabin(BigInt("5")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("6")) == false)
		ASSERT(primalityTestMillerRabin(BigInt("7")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("8")) == false)
		ASSERT(primalityTestMillerRabin(BigInt("9")) == false)
		ASSERT(primalityTestMillerRabin(BigInt("87")) == false)
		ASSERT(primalityTestMillerRabin(BigInt("89")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("329")) == false)
		ASSERT(primalityTestMillerRabin(BigInt("331")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("561")) == false)
		ASSERT(primalityTestMillerRabin(BigInt("563")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("807")) == false)
		ASSERT(primalityTestMillerRabin(BigInt("809")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("2251")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("59561")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("181243")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("14414443")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("10461401779")) == true)
		ASSERT(primalityTestMillerRabin(BigInt("1853028778786433")) == true)
//		ASSERT(primalityTestMillerRabin(BigInt("940461086986004843694934910131104208392131088686023657900173332902199657733778583489")) == true)
 
		ASSERT(BigInt("8").gcd(BigInt("1")) == BigInt("1"))
		ASSERT(BigInt("8").gcd(BigInt("2")) == BigInt("2"))
		ASSERT(BigInt("8").gcd(BigInt("3")) == BigInt("1"))
		ASSERT(BigInt("8").gcd(BigInt("4")) == BigInt("4"))
		ASSERT(BigInt("8").gcd(BigInt("5")) == BigInt("1"))
		ASSERT(BigInt("8").gcd(BigInt("6")) == BigInt("2"))
		ASSERT(BigInt("8").gcd(BigInt("7")) == BigInt("1"))
		ASSERT(BigInt("8").gcd(BigInt("8")) == BigInt("8"))
		ASSERT(BigInt("8").gcd(BigInt("-12")) == BigInt("4"))
		ASSERT(BigInt("-8").gcd(BigInt("12")) == BigInt("-4"))
		ASSERT(BigInt("-8").gcd(BigInt("-12")) == BigInt("-4"))
		ASSERT(BigInt("5").inverse(BigInt("13")) == BigInt("8"))
		ASSERT(BigInt("43").inverse(BigInt("31")) == BigInt("13"))
		ASSERT(BigInt("5").inverse(BigInt("-13")) == BigInt("-5"))
		ASSERT(BigInt("43").inverse(BigInt("-31")) == BigInt("-18"))
		ASSERT(BigInt("18").lcm(BigInt("24")) == BigInt("72"))
		ASSERT(BigInt("18").lcm(BigInt("27")) == BigInt("54"))
 
		clock_t end = clock();
		clock_t elapsed = end - begin;
		cout << (elapsed / CLOCKS_PER_SEC) << "." << setfill('0') << setw(3) << ((elapsed % CLOCKS_PER_SEC) * 1000 / CLOCKS_PER_SEC) << " secs" << endl;
	}
	catch (const string& msg) {
		cerr << msg << endl;
		return 1;
	}
	return 0;
}