def _remove_node(self, node):
    node.prev.next = node.next; node.next.prev = node.prev
def _add_node(self, node):
    node.prev = self.head; node.next = self.head.next
    self.head.next.prev = node; self.head.next = node

def get(self, key):
    if key in self.cache: node = self.cache[key]; self._remove_node(node); self._add_node(node); return node.val
    return -1

def put(self, key, value):
    if key in self.cache: self._remove_node(self.cache[key])
    node = Node(key, value); self._add_node(node); self.cache[key] = node
    if len(self.cache) > self.capacity: lru = self.tail.prev; self._remove_node(lru); del self.cache[lru.key]