class Node(object):
    
    def __init__(self, val):
        self.val = val
        self.next = None

class MyLinkedList(object):

    def __init__(self):
        """
        Initialize data structure here.
        """
        self.head = None  
        self.size = 0  # Number of nodes


    def get(self, index):
        """
        TODO:
        Get the value of the index-th node in the linked list. 
        If the index is invalid, return -1.
        """
        if index >= self.size or index < 0 or self.head == None:
            return -1

        curr = self.head
        
        for i in range(0, index):
            curr = curr.next
            
        return curr.val


    def addAtHead(self, val):
        """
        TODO:
        Add a node of value val before the first element of the linked list. 
        After the insertion, the new node will be the first node of the linked list.
        """
        # node = Node(val)
        # node.next = self.head
        # self.head = node
        # self.size += 1
        
        self.addAtIndex(0, val)
        

    def addAtTail(self, val):
        """
        :type val: int
        :rtype: None
        """
        # curr = self.head
        # if curr is None:
        #     curr = Node(val)
        # else:
        #     while curr.next:
        #         curr = curr.next
        #     curr.next = Node(val)
                
        # self.size += 1
        
        self.addAtIndex(self.size, val)


    def addAtIndex(self, index, val):
        """
        TODO: 
        Add a node of value val before the index=th node in the linked list.
        If index equals to the length of linked list, 
        the node will be appended to the end of linked list.
        
        :type index: int
        :type val: int
        :rtype: None
        """
        if index > self.size :
            return
        
        curr = self.head
        node = Node(val)
        
        if index <= 0:
            node.next = curr
            self.head = node
        else:
            for i in range(index-1):
                curr = curr.next
            node.next = curr.next
            curr.next = node
            
        self.size += 1
        
                
    def deleteAtIndex(self, index):
        """
        TODO:
        Delete the index-th node in the linked list, if the index is valid.
        
        :type index: int
        :rtype: None
        """
        if index >= self.size or index < 0:
            return
        
        curr = self.head
        
        if index == 0:
            self.head = self.head.next
        else:
            for i in range(0, index-1):
                curr = curr.next
            curr.next = curr.next.next
        
        self.size -= 1

        
class Node(object):
    
    def __init__(self, val):
        self.val = val
        self.next = None

class MyLinkedList(object):

    def __init__(self):
        """
        Initialize data structure here.
        """
        self.head = None  
        self.size = 0  # Number of nodes


    def get(self, index):
        """
        TODO:
        Get the value of the index-th node in the linked list. 
        If the index is invalid, return -1.
        """
        if index >= self.size or index < 0 or self.head == None:
            return -1

        curr = self.head
        
        for i in range(0, index):
            curr = curr.next
            
        return curr.val


    def addAtHead(self, val):
        """
        TODO:
        Add a node of value val before the first element of the linked list. 
        After the insertion, the new node will be the first node of the linked list.
        """
        # node = Node(val)
        # node.next = self.head
        # self.head = node
        # self.size += 1
        
        self.addAtIndex(0, val)
        

    def addAtTail(self, val):
        """
        :type val: int
        :rtype: None
        """
        # curr = self.head
        # if curr is None:
        #     curr = Node(val)
        # else:
        #     while curr.next:
        #         curr = curr.next
        #     curr.next = Node(val)
                
        # self.size += 1
        
        self.addAtIndex(self.size, val)


    def addAtIndex(self, index, val):
        """
        TODO: 
        Add a node of value val before the index=th node in the linked list.
        If index equals to the length of linked list, 
        the node will be appended to the end of linked list.
        
        :type index: int
        :type val: int
        :rtype: None
        """
        if index > self.size :
            return
        
        curr = self.head
        node = Node(val)
        
        if index <= 0:
            node.next = curr
            self.head = node
        else:
            for i in range(index-1):
                curr = curr.next
            node.next = curr.next
            curr.next = node
            
        self.size += 1
        
                
    def deleteAtIndex(self, index):
        """
        TODO:
        Delete the index-th node in the linked list, if the index is valid.
        
        :type index: int
        :rtype: None
        """
        if index >= self.size or index < 0:
            return
        
        curr = self.head
        
        if index == 0:
            self.head = self.head.next
        else:
            for i in range(0, index-1):
                curr = curr.next
            curr.next = curr.next.next
        
        self.size -= 1

        
Initialize data structure here. # Number of nodes TODO:         Get the value of the index-th node in the linked list.          If the index is invalid, return -1. TODO:         Add a node of value val before the first element of the linked list.          After the insertion, the new node will be the first node of the linked list. # node = Node(val) # node.next = self.head # self.head = node # self.size += 1 :type val: int         :rtype: None # curr = self.head # if curr is None: #     curr = Node(val) # else: #     while curr.next: #         curr = curr.next #     curr.next = Node(val) # self.size += 1 TODO:          Add a node of value val before the index=th node in the linked list.         If index equals to the length of linked list,          the node will be appended to the end of linked list.                  :type index: int         :type val: int         :rtype: None TODO:         Delete the index-th node in the linked list, if the index is valid.                  :type index: int         :rtype: None