class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self._cache = {}
        self._head = {"prev": None, "next": None, "key": None, "value": None}
        self._tail = {"prev": None, "next": None, "key": None, "value": None}
        self._head["next"] = self._tail
        self._tail["prev"] = self._head

    def _remove(self, node):
        prev_node = node["prev"]
        next_node = node["next"]
        prev_node["next"] = next_node
        next_node["prev"] = prev_node

    def _add_front(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 not in self._cache:
            return -1
        node = self._cache[key]
        self._remove(node)
        self._add_front(node)
        return node["value"]

    def put(self, key, value):
        if self.capacity == 0:
            return
        if key in self._cache:
            node = self._cache[key]
            node["value"] = value
            self._remove(node)
            self._add_front(node)
        else:
            if len(self._cache) >= self.capacity:
                lru = self._tail["prev"]
                self._remove(lru)
                del self._cache[lru["key"]]
            node = {"prev": None, "next": None, "key": key, "value": value}
            self._cache[key] = node
            self._add_front(node)