'''
Created on 10.10.2012

@author: pycz
'''

import copy

class Num:
    def __init__(self):
        self.num='#'
        self.next=None


class LongNum(object):
    def __init__(self,ln=0):
        self.head=Num()
        self.sign='+'
        self._fill(str(ln))
            
    def _addFirst(self,el):
        x=Num()
        x.num=el
        x.next=self.head.next
        self.head.next=x 
    
    def _del(self):
        self.head.next=None
        self.sign="+"
                   
    def _fill(self,ln):
        ln=str(ln)
        self._del()
        self.sign="+"
        if ln and ln[0]=='-':
            self.sign='-'
            ln=ln[1:]
        if ln and ln[0]=='+':
            ln=ln[1:]
        for l in ln:
            x=int(l)
            self._addFirst(x)
        if ln:
            self._reduce_zeros()
            self._isZero()
            
    def _isZero(self):
        if self.head.next and self.head.next.num==0 and self.head.next.next==None:
            self.sign='+'
            return True
        else:
            return False
        
    def __str__(self):
        res=""
        p=self.head.next
        while p!=None:
            res=str(p.num)+res
            p=p.next
        if not self._isZero() and self.sign!='+':
            res='-'+res
        return res
    
    def empty(self):
        return not self.head.next
    
    def __neg__(self):
        res=copy.deepcopy(self)
        if self._isZero():
            return res
        if self.sign=='+':
            res.sign="-"
        else:
            res.sign="+"
        return res
    
    def __abs__(self):
        res=copy.deepcopy(self)
        res.sign="+"
        return res
    
    def _simple_add(self,other):
        '''
        return simple a+b, no signs
        '''
        res=LongNum()
        per=0
        p1=self.head.next
        p2=other.head.next
        p3=res.head
        while not (p1==None and p2==None):
            if p1!=None and p2==None:
                p3.next=Num()
                p3=p3.next
                p3.num=(p1.num+per)%10
                per=(p1.num+per)/10
                p1=p1.next
            if p1==None and p2!=None:
                p3.next=Num()
                p3=p3.next
                p3.num=(p2.num+per)%10
                per=(p2.num+per)/10
                p2=p2.next
            if p1!=None and p2!=None:
                p3.next=Num()
                p3=p3.next            
                p3.num=(p2.num+per+p1.num)%10
                per=(p2.num+per+p1.num)/10
                p2=p2.next
                p1=p1.next
        if per!=0:
            p3.next=Num()
            p3=p3.next
            p3.num=per        
        return res
    
    def _reduce_zeros(self):
        p=self.head.next
        mark=None
        while(p.next):
            if(p.next.num!=0):
                mark=p
            p=p.next
        if mark:
            mark.next.next=None
        else:
            self.head.next.next=None
           
    def _simple_sub(self,other):
        '''
        return simple a-b, no signs, a>=b
        '''
        res=LongNum()
        per=0
        p1=self.head.next
        p2=other.head.next
        p3=res.head
        while p1!=None:
            if p1!=None and p2==None:
                p3.next=Num()
                p3=p3.next                
                p3.num=(p1.num-per)#%10
                if p3.num<0:
                    p3.num+=10
                    per=1
                else:
                    per=0
                p1=p1.next
            if p1!=None and p2!=None:
                p3.next=Num()
                p3=p3.next            
                p3.num=(p1.num-p2.num-per)#%10
                if p3.num<0:
                    p3.num+=10
                    per=1
                else:
                    per=0
                p2=p2.next
                p1=p1.next
        res._reduce_zeros()
        return res                           
    
    def __eq__(self,other):
        p1=self.head.next
        p2=other.head.next
        if self.sign==other.sign:
            equ=True
        else:
            equ=False
            
        while p1 and p2 and equ:
            equ=(p1.num==p2.num)
            p1=p1.next
            p2=p2.next
        if not p1 and not p2 and equ:
            return True
        else:
            return False
    
    def __len__(self):
        '''
        length without sign
        '''
        count=0
        p=self.head
        while(p.next):
            count+=1
            p=p.next
        return count
    
    def reverse(self):
        t1 = self.head.next
        s = None;
        while t1 <> None: 
            p = t1
            t1 = t1.next
            p.next = s
            s = p
        self.head.next = s 
        
    def _low_then(self,other):
        '''
        A<B, A>=0, B>=0
        '''
        if len(self)<len(other):
            return True
        elif len(self)>len(other):
            return False
        else:
            s=copy.deepcopy(self)
            o=copy.deepcopy(other)
            s.reverse()
            o.reverse()
            p1=s.head.next
            p2=o.head.next
            while p1.num==p2.num and p1.next:
                p1=p1.next
                p2=p2.next
            if p1.num<p2.num:
                return True
            else:
                return False
                
    def __lt__(self,other):
        if self.sign=="+" and other.sign=="-":
            return False
        elif self.sign=="-" and other.sign=="+":
            return True
        elif self.sign=="-" and other.sign=="-":
            return other._low_then(self)
        else:
            return self._low_then(other)   
    
    def __le__(self,other):
        if self<other or self==other:
            return True
        else:
            return False
        
    def __ne__(self,other):
        if self==other:
            return False
        else:
            return True
    
    def __gt__(self,other):
        if other<self:
            return True
        else:
            return False
        
    def __ge__(self,other):
        if self<other:
            return False
        else:
            return True    
              
    def __add__(self,other):
        if self.sign=="+" and other.sign=="+":
            return self._simple_add(other)
        elif self.sign=="-" and other.sign=="-":
            res=self._simple_add(other)
            res.sign="-"
            return res
        elif self.sign=="-" and other.sign=="+":
            s=abs(self)
            o=abs(other)
            if o>s:
                res=o._simple_sub(s)
                res.sign="+"
            else:
                res=s._simple_sub(o)
                res.sign="-"
            return res
        else:
            return other+self
       
    def __sub__(self,other):
        return self+(-other)
    
    def _x10mul(self,count=1):
        for i in xrange(count):
            self._addFirst(0)
    
    def _x10div(self,count=1):
        for i in xrange(count):
            self.head.next=self.head.next.next
                
    def _simple_mul(self,other):
        '''
        a*b, a>=0, b>=0
        '''
        summa=LongNum()
        temp=LongNum()
        p2=other.head.next
        level=0
        while p2:
            per=0
            tres=temp.head
            p1=self.head.next
            while p1:
                tres.next=Num()
                tres=tres.next
                tres.num=((p1.num*p2.num)+per)%10
                per=((p1.num*p2.num)+per)/10
                p1=p1.next
            tres.next=Num()
            tres=tres.next
            tres.num=per            
            temp._x10mul(level)
            summa=summa+temp
            temp=LongNum()
            level+=1
            p2=p2.next
        summa._reduce_zeros()
        return summa
    
    def __mul__(self,other):
        if  (self.sign=="+" and other.sign=="+") or (self.sign=="-" and other.sign=="-"):
            return self._simple_mul(other)
        elif  self.sign=="-" and other.sign=="+":
            return -(self._simple_mul(other))
        else:
            return other*self
    
    def __sub_left(self,other):
        '''
        A=aaaa;B=bb; A-B=aaaa-bb00
        '''
        o=abs(other)
        o._x10mul(len(self)-len(other))
        if o<=self:
            return self-o
        else:
            o._x10div(1)
            return self-o
    
    def _simple_div(self,other):
        '''
        A/B; B!=0; no signs
        '''
        s=abs(self)
        o=abs(other)
        res=LongNum()
        delit=copy.deepcopy(o)

        count=0
        while(o<=s):
            count+=1
            o._x10mul()
        o._x10div()
        count-=1
        j=0
        while j<=count:
            C=LongNum()
            i=0
            C._fill(i)
            while C*o<=s:
                i+=1
                C._fill(i)
            i-=1
            res._addFirst(i)
            if i==-1: i=0
            C._fill(i)
            s=s-(C*o)
            if o!=delit:
                o._x10div()
            j+=1
            
        res._reduce_zeros()
        return res
        
        
        
                                
if __name__== "__main__":
    x1=LongNum()
    x2=LongNum()
    y1=1010
    y2=101
    x1._fill(y1)

    x2._fill(y2)
    lol=x1._simple_div(x2)
    print lol
    print y1/y2
 

#    print 
#    print x1+x2
#    print x2+x1