class ListNode:
    def __init__(self, data, prev = None, link = None):
        self.data = data
        self.prev = prev
        self.link = link
        if prev is not None:
            self.prev.link = self
        if link is not None:
            self.link.prev = self

class DoublyLinkedList:
    def __init__(self):
        self._head = None
        self._tail = None
        self._length = 0

    @property
    def head(self):
        return self._head

    @property
    def tail(self):
        return self._tail

    def _addbetween(self, item, before, after):
        node = ListNode(item, before, after)
        if after is self._head:
            self._head = node
        if before is self._tail:
            self._tail = node
        self._length += 1

    def addfirst(self, item):
        self._addbetween(item, None, self._head)

    def addlast(self, item):
        self._addbetween(item, self._tail, None)

    def _remove(self, node):
        before, after = node.prev, node.link
        if node is self._head:
            self._head = after
        else:
            before.link = after
        if node is self._tail:
            self._tail = before
        else:
            after.prev = before
        self._length -= 1
        return node.data

    def removefirst(self):
        return self._remove(self._head)

    def removelast(self):
        return self._remove(self._tail)

    def __len__(self):
        return self._length

class DoublyLinkedNumber(DoublyLinkedList):
    def __init__(self):
        self._L = DoublyLinkedList()

    def tolinkednumber(self, string):
        for i in range(len(string)):
            if string.startswith('0'): string = string[1:]
        for s in string:
            self._L.addlast(s)

    def __str__(self):
        storedstring = ''
        for l in range(self._L.__len__()):
            ph = self._L.removefirst()
            storedstring = storedstring + str(ph)
            self._L.addlast(ph)
        return storedstring

    def head(self):
        return self._L._head

    def tail(self):
        return self._L._tail

    def addfirst(self, item):
        self._L.addfirst(item)

## To-Do : Addition of numbers present in the 2 DoublyLinkedLists.
## Start from the tail and traverse backwards.
## Perform addition on data of nodes and account for carry generated
## Store the sum in a new doubly linked list
def sumlinkednumbers(dll1, dll2):
    dllsum = DoublyLinkedNumber()
    c1 = dll1.tail()
    c2 = dll2.tail()
    carry = 0

    while c1 or c2 is not None:
        #print('Start---')

        if c2 is None:
            sum = int(c1.data)
            #print(c1.data)
            #print('SUM: ', sum)
        elif c1 is None:
            sum = int(c2.data)
            #print(c2.data)
            #print('SUM: ', sum)
        else:
            sum = int(c1.data) + int(c2.data)
            #print(c1.data)
            #print(c2.data)
            #print('SUM: ', sum)

        if carry > 0:
            sum = int(sum) + carry
            carry = 0
            #print('Calc carry', sum, carry)
        if int(sum) > 10:
            carry += 1
            sum = int(sum) - 10
            #print('Has carry', sum, carry)

        dllsum.addfirst(sum)

        if c2 is None:
            c1 = c1.prev
        elif c1 is None:
            c2 = c2.prev
        else:
            c1 = c1.prev
            c2 = c2.prev
        #print('---End')
    return dllsum