#define inandoutn
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
using namespace std ;
const int IntegerLen=1000;
class Integer{
public:
Integer(int num=0)//利用整数初始化 有待改进
{
if(num<0)
{
sign=-1;
num=-num;
}
else sign=1;
for(int i=0;i<IntegerLen;i++)//到后面就是赋值0了
{
(*this)[i]=num%10;
num/=10;
}
}
Integer(const Integer& obj)
{
sign=obj.sign;
for(int i=0;i<IntegerLen;i++) (*this)[i]=obj[i];
}
Integer operator = (const Integer& another)//同类赋值
{
int i;
(*this).sign=another.sign;
for(i=0;i<IntegerLen;i++)
(*this)[i]=another[i];
return *this;
}
Integer operator =(const char *p )//用字符组赋值
{
memset(NumArray,0,sizeof(NumArray));
if(*p=='-')
{
sign=-1;
*(p++);
}
else sign=1;
int len=strlen(p);
p+=(len-1);
for(int i=0;i<len;i++)
{
(*this)[i]=*(p-i)-'0';
}
}
Integer operator + (const Integer& another) const
{
int i;
Integer result;
if(sign==another.sign){
for(i=0;i<IntegerLen;i++){
result[i]=(*this)[i]+another[i]+result[i];
while(result[i]>=10){
result[i]-=10;
result[i+1]++;
}
}
result.sign=(*this).sign;
}
else result=(*this)-(-another);
return result;
}
Integer operator - (const Integer& another) const
{
int i;
Integer result;
const Integer *max,*min;
if((*this)==another) return Integer(0);
if(sign==another.sign){
if((*this).absolute()>another.absolute()){
max=this;
min=&another;
}else{
max=&another;
min=this;
}
for(i=0;i<IntegerLen;i++){
result[i]=(*max)[i]-(*min)[i]+result[i];
while(result[i]<0){
result[i]+=10;
result[i+1]--;
}
}
if(max==this) result.sign=(*this).sign;
else result.sign=-(*this).sign;
}else{
result=(*this)+(-another);
}
return result;
}
Integer operator - () const
{
Integer result;
result=*this;
if(result!=Integer(0))
result.sign=-sign;
return result;
}
Integer operator * (const Integer& another) const
{
Integer result,temp;
int i,j;
if((*this)==0||another==0) return result;
for(i=0;i<IntegerLen;i++){
temp=Integer(0);
for(j=0;j<IntegerLen-i;j++){
temp[i+j]=(*this)[i]*another[j]+temp[i+j];
while(temp[i]>=10){
temp[i]-=10;
temp[i+1]++;
}
}
result=result+temp;
}
if(sign==another.sign) result.sign=1;
else result.sign=-1;
return result;
}
Integer operator / (const Integer& another) const
{
int i,j,margin;
Integer result,dividend=(*this).absolute(),divisor=another.absolute();
if(divisor>dividend) return Integer(0);
i=IntegerLength();
j=another.IntegerLength();
margin=i-j;
divisor.augment(margin);
while(margin>=0){
if(dividend>=divisor){
dividend=dividend-divisor;
result.NumArray[IntegerLen-margin-1]++;
}else{
margin--;
divisor.augment(-1);
}
}
if(sign==another.sign) result.sign=1;
else result.sign=-1;
return result;
}
Integer operator % (const Integer& another) const
{
Integer result;
result=(*this)-((*this)/another)*another;
return result;
}
bool operator > (const Integer& another) const
{
int i;
if(sign>another.sign) return true;
else if(sign<another.sign) return false;
else if(sign==1){
for(i=IntegerLen-1;i>=0;i--)
if((*this)[i]>another[i]) return true;
else if((*this)[i]<another[i]) return false;
}else{
for(i=IntegerLen-1;i>=0;i--)
if((*this)[i]>another[i]) return false;
else if((*this)[i]<another[i]) return true;
}
return false;
}
bool operator < (const Integer& another) const
{
int i;
if(sign>another.sign) return false;
else if(sign<another.sign) return true;
else if(sign==1){
for(i=IntegerLen-1;i>=0;i--)
if((*this)[i]>another[i]) return false;
else if((*this)[i]<another[i]) return true;
}else{
for(i=IntegerLen-1;i>=0;i--)
if((*this)[i]>another[i]) return true;
else if((*this)[i]<another[i]) return false;
}
return false;
}
bool operator == (const Integer& another) const
{
if(!(*this>another)&&!(*this<another)) return true;
else return false;
}
bool operator != (const Integer& another) const
{
if(*this==another) return false;
else return true;
}
bool operator >= (const Integer& another) const
{
if(*this<another) return false;
else return true;
}
bool operator <= (const Integer& another) const
{
if(*this>another) return false;
else return true;
}
friend ostream& operator << (ostream& stream,const Integer& obj)
{
int i;
if(obj.sign==-1) stream<<'-';
for(i=0;i<IntegerLen&&obj.NumArray[i]==0;i++);
if(i==IntegerLen) stream<<0;
else for(;i<IntegerLen;i++) stream<<obj.NumArray[i];
return stream;
}
friend istream& operator >> (istream& stream,Integer& obj)
{
int n,i;
char input[IntegerLen];
stream>>input;
n=strlen(input);
for(i=0;n-i-1>0;i++){
obj[i]=input[n-i-1]-'0';
}
if(input[n-i-1]=='-') obj.sign=-1;
else
{
obj[i]=input[n-1-i++]-'0';
obj.sign=1;
}
for(;i<IntegerLen;i++) obj[i]=0;
return stream;
}
private:
Integer absolute() const
{
Integer result;
result=*this;
result.sign=1;
return result;
}
int IntegerLength() const
{
int i,result=0;
for(i=0;i<IntegerLen&&NumArray[i]==0;i++);
result=IntegerLen-i;
return result;
}
void augment(int n)
{
int i;
if(n>=0){
for(i=0;i<IntegerLen;i++)
if(i<IntegerLen-n) NumArray[i]=NumArray[i+n];
else NumArray[i]=0;
}else{
for(i=IntegerLen-1;i>=0;i--)
if(i>=-n) NumArray[i]=NumArray[i+n];
else NumArray[i]=0;
}
}
int& operator [] (int index)
{
return NumArray[IntegerLen-index-1];
}
const int& operator [] (int index) const
{
return NumArray[IntegerLen-index-1];
}
int NumArray[IntegerLen];
int sign;
};
int main()
{
#ifdef inandout
freopen("C:\Users\lx\Desktop\1.in","r",stdin);
#endif
return 0;
}