class LRUCache : public Cache {
private:
    int capacity;

public:
    LRUCache(int cap) {
        cp = cap;
        capacity = cap;
        tail = NULL;
        head = NULL;
    }

    void set(int key, int value) override {
        if (mp.find(key) != mp.end()) {
            Node* node = mp[key];
            node->value = value;   
            
            if (node->prev != NULL) {
                node->prev->next = node->next;
                if (node->next != NULL)
                    node->next->prev = node->prev;
                else
                    tail = node->prev;
                node->prev = NULL;
                node->next = head;
                head->prev = node;
                head = node;
            }
        } else {
           
            Node* node = new Node(NULL, head, key, value);
            if (head != NULL)
                head->prev = node;
            head = node;
            if (tail == NULL)
                tail = node;

            if (mp.size() == capacity) {
                mp.erase(tail->key);
                tail = tail->prev;
                delete tail->next;
                tail->next = NULL;
            }

            mp[key] = node;
        }
    }

    int get(int key) override {
        if (mp.find(key) != mp.end()) {
            Node* node = mp[key];

            if (node->prev != NULL) {
                node->prev->next = node->next;
                if (node->next != NULL)
                    node->next->prev = node->prev;
                else
                    tail = node->prev;
                node->prev = NULL;
                node->next = head;
                head->prev = node;
                head = node;
            }

            return node->value;
        }
        return -1;
    }
};