//
// LiBigInt.cpp   Implementation files
//
// Free for educational use.. By Chung-Chih Li, 8-21-2003
//


#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdlib>
#include <time.h>
#include <cmath>
#include "LiBigInt.h"


using namespace std;

LiBigi::LiBigi()
{
    number.reserve(70);  // run a bit faster when 32 
	mysign = 1;
}


LiBigi::LiBigi(long n)
{
    number.reserve(32);
    number.resize(0);
	if (n < 0) 
	{
		mysign=-1;
		n *= -1;
	}
	else mysign = 1;
    while (n != 0)
    {
            number.push_back(n % 10);
            n /= 10;
    }
}


void LiBigi::shift_left_10()
{
    number.push_back(0);
    for (int i = number.size()-1; i > 0; i--)
        number[i] = number[i-1];
    number[0]=0;
}

char LiBigi::shift_right_10()
{
    char d = number[0];
    for (int i = 0; i < number.size()-1; i++)
        number[i] = number[i+1];
    number.pop_back();
    return d;
}

char LiBigi::operator [](int i)
{
    if (i >= number.size()) return 0;
    return number[i];
}

void cut_leading_zero(LiBigi &n)
{
    while (n.number.size()) 
    {
        if (n.number[n.number.size()-1]) break;
        n.number.pop_back();
    }
}

ostream & operator << (ostream & outputstream, LiBigi & n)
{
    int i = n.number.size();
	if (i == 0)  outputstream << 0;
	if (n.mysign == -1) outputstream << "-";
    while (i > 0)
        outputstream << int(n.number[--i]);
    return  outputstream;
}

istream & operator >> (istream & inputstream, LiBigi & n)
{
    string s;
    inputstream >> s;
    n.number.resize(0);
    for (int i = s.length(); i > 0; i--)
        n.number.push_back(s[i-1]-48);
	if (s[0] == '-')
	{
		n.number.pop_back();
		n.mysign =-1;
	}
	else n.mysign=1;
    return  inputstream;
}


LiBigi ABS(LiBigi a)
{
	LiBigi b;
	b=a;
	b.mysign=1;
	return b;
}

LiBigi operator + (LiBigi a, LiBigi b)
{
    char s,carry=0;
    LiBigi sum; // the sum
    int i=0;

	if (a.mysign == b.mysign) 
	{
		sum.mysign = a.mysign;
		while (i < a.number.size() || i < b.number.size())
		{
			s = a[i]+b[i]+carry;
			sum.number.push_back(s%10);
			carry = s/10;
			i++;
		}
		if (carry) sum.number.push_back(carry);
		return sum;
	}
	if (b.mysign == -1)
		return (a - ABS(b));
	return (b - ABS(a));

}


// Helper a-b, a,b >=0  and a > b;
LiBigi proper_sub(LiBigi a, LiBigi b) // return a if a < b
{
    char borrow=0;
    LiBigi diff; // the diff
    int i=0, max = (a.number.size() > b.number.size() ? a.number.size()
                                                      : b.number.size());
    while (i < max)
    {
        if ( a[i] < b[i] + borrow)
        {
            diff.number.push_back(a[i]+10-b[i]-borrow);
            borrow = 1;
        }
        else
        {
            diff.number.push_back(a[i]-b[i]-borrow);
            borrow = 0;
        }
        i++;
    }
    if (borrow) return a;
    cut_leading_zero(diff);
	diff.mysign = 1;
    return diff;
}


LiBigi operator - (LiBigi a, LiBigi b) 
{
	LiBigi aa,ab, diff;
	aa = ABS(a);
	ab = ABS(b);
	if (b.mysign == -1) return a+ab; // a - (-1);
	if (a.mysign == -1)  // -1 - (1);
	{
		diff = aa+ab;
		diff.mysign = -1;
		return diff;
	}
	// 3-2 (both are positiveP
	if (a >= b) return proper_sub(a,b);
	diff = proper_sub(b,a);
	diff.mysign = -1;
	return diff;
}



LiBigi operator * (LiBigi a, LiBigi b)
{
    int i;
    char carry,dp,dm;
    
    LiBigi tp,fp; // the temp product and final product
    
    while (b.number.size() != 0)
    {
        dm = b.shift_right_10();
        if (dm == 0) 
        {
            a.shift_left_10();
            continue;
        }
        tp.number.resize(0);
        carry=0;
        for (i=0;i<a.number.size();i++)
        {
            dp = a[i]*dm+carry;
            tp.number.push_back(dp%10);
            carry = dp/10;
        }
        if (carry) tp.number.push_back(carry);
        fp = fp+tp;
        a.shift_left_10();
    }
	fp.mysign = a.mysign*b.mysign;
    return fp;
}


bool operator ==  (LiBigi a, LiBigi b)
{
	if (a.mysign != b.mysign) return false;
    cut_leading_zero(a);
    cut_leading_zero(b);

    if (a.number.size() != b.number.size()) return false;
    for (int i=0; i<b.number.size(); i++)
        if (a[i] != b[i]) return false;
    return true;
}

bool operator !=  (LiBigi a, LiBigi b)
{
    return !(a==b);
}


LiBigi operator ++ (LiBigi & a)
{
    LiBigi one(1);
    a = a + one;
    return a;
}


LiBigi operator ^ (LiBigi a, LiBigi b)
{
    
    LiBigi p(1), i(0); 

    while(i != b)
    {
        p = p*a;
        ++i;
    }
    return p;
}


long to_long(LiBigi n)
{
    long i=0;
    while (n.number.size())
    {
        i = i*10 + n[n.number.size()-1];
        n.number.pop_back();
    }
	i = i*n.mysign;
    return i;
}


bool abs_ge (LiBigi a, LiBigi b)  //both are positive
{
    if (a.number.size() > b.number.size()) return true;
    if (a.number.size() < b.number.size()) return false;
    for (int i=b.number.size(); i>0; i--)
    {
        if (a[i-1] > b[i-1]) return true;
        if (a[i-1] < b[i-1]) return false;
    }
    return true;
}


bool operator >= (LiBigi a, LiBigi b)  
{
	LiBigi aa, ab;
	aa = ABS(a);
	ab = ABS(b); 

	if (a.mysign > b.mysign) return true;
	if (a.mysign < b.mysign) return false;
	if (a.mysign == 1) return abs_ge(a,b);
	return abs_ge(b,a);
}


bool operator > (LiBigi a, LiBigi b)  
{
	return ((a >= b) && (a != b));
}


bool operator < (LiBigi a, LiBigi b)  
{
	return (!(a >= b));
}

bool operator <= (LiBigi a, LiBigi b)  
{
	return ((a < b) || (a == b));
}


LiBigi operator % (LiBigi oa, LiBigi m)   // m>0;
{
	if (0 >= m) 
	{
		cout << "Error in % operation" << m << "<0;";
		return oa;
	}
	LiBigi q,a=ABS(oa), mt=m;

	q = a/m;
	a = a - m*q;
	a.mysign = oa.mysign;
    if (a.mysign == 1) return a;
    return a+m;
}

LiBigi operator / (LiBigi sa, LiBigi sdor)  
{
    LiBigi a,dor,inv_q, q, mt;
	a = ABS(sa);
	dor = ABS(sdor);
    char d;
    cut_leading_zero(a);
    cut_leading_zero(dor);
    mt = dor;

    while (a.number.size() > mt.number.size()) mt.shift_left_10();
    while (a >= dor || mt.number.size() >= dor.number.size())
    {
        d=0;
        while (a >= mt) {d++; a = a - mt;}
        mt.shift_right_10();
        inv_q.number.push_back(d);
    }
    while (inv_q.number.size() !=0) 
    {
        q.number.push_back(inv_q.number[inv_q.number.size()-1]);
        inv_q.number.pop_back();        
    }
    cut_leading_zero(q);
	q.mysign = sa.mysign*sdor.mysign;
    return q;
}

void half(LiBigi &n)
{
    int i=n.number.size();
    if (i==0) return;
    char newrem,rem=0;
    while (i >0)
    {
        i--;
        if (n[i] % 2) newrem=10;
        else newrem=0;
        n.number[i] = (rem+n.number[i])/2;
        rem = newrem;
    }
    cut_leading_zero(n);
}




/*
void main()
{

	cout << "I'm here";
}
*/