#include <iostream>
#include <string>  
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>

class bigint
{
private:
	char sign;		//+:0, -:1					
	unsigned *dats;	//가장 뒷자리가 dats[0]에 저장
	unsigned len;	//dats배열 길이

public:
	unsigned cona2u(char*);

	bigint();
	~bigint();
	bigint(const int);
	bigint(const char*);
	bigint(const bigint &);

	unsigned resize(unsigned);	//길이조절
	unsigned resize();			//앞의 0 지우기
	bigint abs();				//절대값
	bigint negative(unsigned);	//1의보수	

	int cmp(bigint &b);			//strcmp와 리턴값 같음

	bigint _or(bigint &b);		//this에 저장
	bigint _and(bigint &b);		//this에 저장
	bigint _xor(bigint &b);		//this에 저장
	bigint shr(unsigned n);		//this에 (this>>n)을 저장
	bigint shl(unsigned n);		//this에 (this<<n)을 저장	

	bigint add(bigint &b);		//this에 (this+b)를 저장, 리턴
	bigint sub(bigint &b);		//this에 (this-b)를 저장, 리턴
	bigint mul(bigint &b);		//(this*b)를 리턴
	bigint mul_lr(bigint &b);	//(this*b)를 리턴, A la russe알고리즘, 느려
	bigint div(bigint &b, int);	//(this/b)또는 (this%b)리턴

	char* con10();	//10진수 출력

	bigint operator=(const int);
	bigint operator=(const bigint &);
	bigint operator=(const char*);

	friend bigint operator|(bigint, bigint);
	friend bigint operator&(bigint, bigint);
	friend bigint operator^(bigint, bigint);
	friend bigint operator+(bigint, bigint);
	friend bigint operator-(bigint, bigint);
	friend bigint operator*(bigint, bigint);
	friend bigint operator/(bigint, bigint);
	friend bigint operator%(bigint, bigint);

	friend bool operator<(bigint, bigint);
	friend bool operator<=(bigint, bigint);
	friend bool operator>(bigint, bigint);
	friend bool operator>=(bigint, bigint);
	friend bool operator==(bigint, bigint);
	friend bool operator!=(bigint, bigint);

	bigint operator|=(bigint);
	bigint operator&=(bigint);
	bigint operator^=(bigint);
	bigint operator+=(bigint);
	bigint operator-=(bigint);
	bigint operator*=(bigint);
	bigint operator/=(bigint);
	bigint operator%=(bigint);


	
	friend std::ostream& operator <<( std::ostream& os, bigint b );
	friend std::istream& operator >>( std::istream& is, bigint& b );
};

unsigned bigint::cona2u(char *src)
{
	unsigned ten, sum, eos=strlen(src)-1;

	for(sum=0, ten=1; (int)eos>=0 && ten<=100000000; ten*=10, eos--)
	{
		sum+=ten*(src[eos]-'0');
		src[eos]=0;
	}
	return sum;
}

bigint::bigint()
{
	len=1;
	sign=0;
	dats=(unsigned*)calloc(1,sizeof(unsigned));
}

bigint::~bigint()
{
	free(dats);
}

bigint::bigint(const int src)
{
	len=1;
	sign=0;
	dats=(unsigned*)malloc(sizeof(unsigned)*len);
	dats[0]=src;
}

bigint::bigint(const char *src)
{
	char *str=(char*)malloc(sizeof(char)*(strlen(src)+1));

	sign=0;
	strcpy(str, src);
	if(src[0]=='-')
		strcpy(str,src+1), sign=1;
	if(src[0]=='+')
		strcpy(str,src+1);

	len=(strlen(src)-1)/9 + 1;
	dats=(unsigned*)malloc(sizeof(unsigned)*len);
	unsigned i;
	for(i=0; i<len; i++)
	{
		dats[i]=cona2u(str);
	}
	free(str);
	shl(len*32);	//

	unsigned j, lmt=len/2;
	for(i=(len/2)*32; i; i--)
	{
		shr(1);
		for(j=len-1; j>=lmt; j--)
		{
			if(dats[j]>=2147483648)
				dats[j]-=1647483648;
		}
	}
}

bigint::bigint(const bigint &src)
{
	len=src.len;
	sign=src.sign;
	dats=(unsigned*)malloc(sizeof(unsigned)*len);
	memcpy(dats, src.dats, sizeof(unsigned)*len);
}

unsigned bigint::resize(unsigned len_new)
{
	if(len==len_new)
		return len;
	unsigned *new_p=(unsigned*)malloc(sizeof(unsigned)*len_new);		//
	memcpy(new_p, dats, sizeof(unsigned)*((len<len_new)?len:len_new));	//이부분에 realloc(dats, sizeof(unsigned)*len_new)쓰면 왜 값이 바뀌나요
	free(dats);															//
	dats=new_p;															//

	if(len < len_new)
		memset(dats+len, 0, sizeof(unsigned)*(len_new-len));
	len=len_new;
	return len;
}

unsigned bigint::resize()
{
	unsigned i;
	for(i=len-1; dats[i]==0; i--);
	i++;
	if(i)
		resize(i);
	else
		resize(1);
	return len;
}

bigint bigint::abs()
{
	bigint toreturn(*this);
	toreturn.sign=0;
	return toreturn;
}

//1의 보수
bigint bigint::negative(unsigned len_new)
{
	bigint toreturn(*this);
	toreturn.resize(len_new);
	for(unsigned i=0; i<len_new; i++)
		toreturn.dats[i]=~toreturn.dats[i];
	return toreturn;
}

int bigint::cmp(bigint &b)
{
	if(sign==1 && b.sign==0)
		return -1;
	if(sign==0 && b.sign==1)
		return 1;

	int left=1, right=-1;	
	if(sign==1 && b.sign==1)
		left=-1, right=1;

	if(len>b.len)
		return left;
	if(len<b.len)
		return right;

	for(int i=len-1; i>=0; i--)
	{
		if(dats[i]>b.dats[i])
			return left;
		if(dats[i]<b.dats[i])
			return right;
	}
	return 0;
}

bigint bigint::_or(bigint &b)
{
	if(len<b.len)
		resize(b.len);
	unsigned i;
	for(i=0; i<len; i++)
		dats[i]|=b.dats[i];
	return *this;
}

bigint bigint::_and(bigint &b)
{
	if(len<b.len)
		resize(b.len);
	unsigned i;
	for(i=0; i<len; i++)
		dats[i]&=b.dats[i];
	return *this;
}

bigint bigint::_xor(bigint &b)
{
	if(len<b.len)
		resize(b.len);
	unsigned i;
	for(i=0; i<len; i++)
		dats[i]^=b.dats[i];
	return *this;
}

bigint bigint::shr(unsigned n)
{
	unsigned move=n>>5, cut=n&31, i, j, tmp;
	dats[0]=dats[move]>>cut;
	for(i=1; i<len-move; i++)
	{
		for(j=0, tmp=dats[i+move]; j<32-cut; j++)	//dats[i+1]=dats[i+1]|(dats[i+move]<<(32-cut));
			tmp<<=1;								//
		dats[i-1]|=tmp;
		dats[i]=dats[i+move]>>cut;  
	}


	resize(len-move);//옮겨진 부분 삭제
	resize();
	return *this;
}

bigint bigint::shl(unsigned n)
{
	unsigned move=n>>5, cut=n&31, i, j, tmp;

	resize(len+move+1);
	dats[len-1]=dats[len-move-1]<<cut;
	for(i=len-2; (int)i>=(int)move; i--)
	{
		for(j=0, tmp=dats[i-move]; j<32-cut; j++)	//dats[i+1]=dats[i+1]|(dats[i-move]>>(32-cut));
			tmp>>=1;								//
		dats[i+1]=dats[i+1]|tmp;
		dats[i]=dats[i-move]<<cut;
	}
	memset(dats, 0, sizeof(unsigned)*move);//뒤에 옮겨진 부분 0으로

	resize();
	return *this;
}

bigint bigint::add(bigint &b)
{
	long long carry=0;
	unsigned i;
	resize( ((b.len>len)?b.len:len) + 1 );

	for(i=0; i<b.len; i++)
	{
		carry = (long long)dats[i] + (long long)b.dats[i] + carry;
		dats[i]=carry&(((long long)1<<32)-1);
		carry>>=32;
	}

	for(; carry; i++)
	{
		carry=(long long)dats[i] + carry;
		dats[i]=carry&(((long long)1<<32)-1);
		carry>>=32;
	}

	resize();

	return *this;
}

//1의 보수 사용
bigint bigint::sub(bigint &b)
{
	bigint subtrahend(b);	//감수
	//resize(len);
	unsigned len_new=((len>b.len)?len:b.len);
	subtrahend=subtrahend.negative(len_new);

	add(subtrahend);
	if(len > len_new)//자리올림수있으면
	{
		resize(len_new);
		add((bigint)1);
	}
	else//자리올림수 없으면
	{
		*this=negative(len_new);
		sign=1;
	}
	return *this;
}

bigint bigint::mul(bigint &b)
{
	bigint result, tmp;
	unsigned i, j;
	long long carry;
	for(i=0; i<b.len; i++)
	{
		tmp.resize(len+1+i);
		for(carry=j=0; j<len; j++)
		{
			carry=(long long)dats[j]*(long long)b.dats[i]+carry;
			tmp.dats[j+i]=(unsigned)carry&(((long long)1<<32)-1);
			carry>>=32;
		}
		tmp.dats[j+i]=(unsigned)carry;
		result.add(tmp);
		memset(tmp.dats, 0, sizeof(unsigned)*tmp.len);
	}
	result.resize();
	return result;	
}

bigint bigint::mul_lr(bigint &b)
{
	bigint sum(0), tmp(b);

	while( cmp((bigint)0) != 0)
	{
		if(dats[0]&1)
			sum.add(tmp);
		shr(1);
		tmp.shl(1);
	}
	return sum;
}

bigint bigint::div(bigint &b, int ask_mod=0)
{
	bigint r=*this, q=0, tmp=b, one=1;
	unsigned i;

	for(i=0;tmp.cmp(r)<=0;tmp.shl(1),i++);
	i--;
	tmp.shr(1);
	one.shl(i);

	while(b.cmp(r)<=0)//b<=r
	{
		for(;tmp.cmp(r)>0;tmp.shr(1),one.shr(1));
		q._or( one );
		r.sub(tmp);
	}
	*this=q;
	if(ask_mod)
		return r;
	return *this;
}

char* bigint::con10()
{
	bigint tmp(*this);
	unsigned i, j, lmt=tmp.len;
	char *str, str_tmp[10];

	for(i=tmp.len*32; i; i--)
	{
		for(j=tmp.len-1; j>=lmt; j--)
		{
			if(tmp.dats[j] >= 500000000)
				tmp.dats[j]+=1647483648;
		}
		tmp.shl(1);
	}

	i=tmp.len-1;
	str=(char *)calloc((tmp.len-lmt)*9, sizeof(char));
	sprintf(str_tmp,"%u", tmp.dats[i]);
	strcat(str, str_tmp);
	if(i)
	{
		for(--i; i>=lmt; i--)
		{
			sprintf(str_tmp,"%09u",tmp.dats[i]);
			strcat(str, str_tmp);
		}
	}
	return str;
}

bigint bigint::operator=(const int src)
{
	resize(1);
	sign=0;	
	dats[0]=src;
	if(src<0)
		sign=1, dats[0]*=-1;
	return *this;
}

bigint bigint::operator=(const bigint &src)
{
	resize(src.len);
	sign=src.sign;
	memcpy(dats, src.dats, sizeof(unsigned)*len);
	return *this;
}

bigint bigint::operator=(const char *src)
{
	char *str=(char*)malloc(sizeof(char)*(strlen(src)+1));

	sign=0;
	strcpy(str, src);
	if(src[0]=='-')
		strcpy(str,src+1), sign=1;
	if(src[0]=='+')
		strcpy(str,src+1);

	resize((strlen(src)-1)/9 + 1);
	unsigned i;
	for(i=0; i<len; i++)
	{
		dats[i]=cona2u(str);
	}
	free(str);
	shl(len*32);

	unsigned j, lmt=len/2;
	for(i=(len/2)*32; i; i--)
	{
		shr(1);
		for(j=len-1; j>=lmt; j--)
		{
			if(dats[j]>=2147483648)
				dats[j]-=1647483648;
		}
	}

	return *this;
}

bigint operator|(bigint a, bigint b)
{
	return a._or(b);
}

bigint operator&(bigint a, bigint b)
{
	return a._and(b);
}

bigint operator^(bigint a, bigint b)
{
	return a._xor(b);
}

bigint operator+(bigint a, bigint b)
{
	if(a.sign==b.sign)
		return a.add(b);
	if(a.sign==0 && b.sign==1)
		return a.sub(b);
	//a.sign==1 && b.sign==0
	return b.sub(a);
}

bigint operator-(bigint a, bigint b)
{
	if(a.sign==1 && b.sign==1)
	{
		b.sign=0;
		if((a.abs()).cmp(b.abs())==1)
			b.sign=1;
		b.sub(a);
		return b;
	}
	if(a.sign==0 && b.sign==0)
		return a.sub(b);
	if(a.sign==0 && b.sign==1)
		return a.add(b);
	//a.sign==1 && b.sign==0
	a.add(b);
	a.sign=1;
	return a;
}

bigint operator*(bigint a, bigint b)
{
	bigint toreturn=a.mul(b);
	toreturn.sign=a.sign^b.sign;
	return toreturn;
}

bigint operator/(bigint a, bigint b)
{
	bigint toreturn=a.div(b);
	toreturn.sign=a.sign^b.sign;
	return toreturn;
}

bigint operator%(bigint a, bigint b)
{
	bigint toreturn=a.div(b,1);
	toreturn.sign=a.sign;
	return toreturn;
}

bool operator<(bigint a, bigint b)
{
	if(a.cmp(b)<0)
		return true;
	return false;
}

bool operator<=(bigint a, bigint b)
{
	if(a.cmp(b)<=0)
		return true;
	return false;
}

bool operator>(bigint a, bigint b)
{
	if(a.cmp(b)>0)
		return true;
	return false;
}

bool operator>=(bigint a, bigint b)
{
	if(a.cmp(b)>=0)
		return true;
	return false;
}

bool operator==(bigint a, bigint b)
{
	if(a.cmp(b)==0)
		return true;
	return false;
}

bool operator!=(bigint a, bigint b)
{
	if(a.cmp(b)==0)
		return false;
	return true;
}

bigint bigint::operator|=(bigint b)
{
	if(len!=b.len)
	{
		resize((len>b.len)?len:b.len);
		b.resize((len>b.len)?len:b.len);
	}
	_or(b);
	resize();
	return *this;
}

bigint bigint::operator&=(bigint b)
{
	if(len!=b.len)
	{
		resize((len>b.len)?len:b.len);
		b.resize((len>b.len)?len:b.len);
	}
	_and(b);
	resize();
	return *this;
}
bigint bigint::operator^=(bigint b)
{
	if(len!=b.len)
	{
		resize((len>b.len)?len:b.len);
		b.resize((len>b.len)?len:b.len);
	}
	_xor(b);
	resize();
	return *this;
}

bigint bigint::operator+=(bigint b)
{
	if(sign==b.sign)
		return add(b);
	if(sign==0 && b.sign==1)
		return sub(b);
	//a.sign==1 && b.sign==0
	return *this=b.sub(*this);
}

bigint bigint::operator-=(bigint b)
{
	if(sign==1 && b.sign==1)
	{
		b.sign=0;
		if((abs()).cmp(b.abs())==1)
			b.sign=1;
		return *this=b.sub(*this);
	}
	if(sign==0 && b.sign==0)
		return sub(b);
	if(sign==0 && b.sign==1)
		return add(b);
	//a.sign==1 && b.sign==0
	sign=1;
	return add(b);
}

bigint bigint::operator*=(bigint b)
{
	*this=mul(b);
	sign=sign^b.sign;
	return *this;
}

bigint bigint::operator/=(bigint b)
{
	*this=div(b);
	sign=sign^b.sign;
	return *this;
}

bigint bigint::operator%=(bigint b)
{
	*this=div(b,1);
	return *this;
}

std::ostream& operator <<(std::ostream& os, bigint b )
{
	char *tmp=b.con10();
	os << ((b.sign == 1)? "-": "") << tmp;
	free(tmp);

	return os;
}

std::istream& operator >>(std::istream& is, bigint& b )
{
	std::string numstr;
	is >> numstr;
	b = numstr.c_str();

	return is;
}

int main()
{
	return 0;
}