include

include

include

include

include

include

include

using namespace std;

struct Node { Node* next; Node* prev; int value; int key; Node(Node* p, Node* n, int k, int val) :prev(p), next(n), key(k), value(val) {}; Node(int k, int val) :prev(NULL), next(NULL), key(k), value(val) {}; };

class Cache {

protected: map mp; //map the key to the node in the linked list int cp; //capacity Node* tail; // double linked list tail pointer Node* head; // double linked list head pointer Cache(int capacity) : cp(capacity) { tail = nullptr; head = nullptr; } public: virtual void set(int, int) = 0; //set function virtual int get(int) = 0; //get function virtual ~Cache() { Node* p; while (head) { p = head; head = head->next; delete p; } }

};

class LRUCache final : public Cache { public: LRUCache(int capacity) : Cache(capacity) { }

void set(int key, int value) override {
    auto result = mp.find(key);
    if (result != mp.end()) {
        Node* p = result->second;
        p->value = value;
        moveToFrontNode(p);
    } else {
        Node* p = new Node(key, value);
        AddToFrontNode(p);
        mp[key] = p;
        if (mp.size() > cp) {
            mp.erase(tail->key);
            removeLastNode();
        }
    }
}

int get(int key) override {
    auto result = mp.find(key);
    if (result != mp.end()) {
        Node* p = result->second;
        moveToFrontNode(p);
        return p->value;
    }
    return -1;
}

private: void moveToFrontNode(Node* p) { if (p == head) return; if (p == tail) { tail = p->prev; tail->next = nullptr; } else { p->prev->next = p->next; p->next->prev = p->prev; } p->prev = nullptr; p->next = head; head = p; p->next->prev = p; }

void AddToFrontNode(Node* p) {
    p->prev = nullptr;
    p->next = head;
    head = p;
    if (p->next) {
        p->next->prev = p;
    }
    if (!tail) {
        tail = p;
    }
}

void removeLastNode() {
    if (tail) {
        Node* p = tail;
        tail = tail->prev;
        if (tail) {
            tail->next = nullptr;
        }
        else {
            head = nullptr;
        }
        delete p;
    }
}

};

int main() { int n, capacity, i; cin >> n >> capacity; LRUCache l(capacity); for (i = 0; i < n; i++) { string command; cin >> command; if (command == "get") { int key; cin >> key; cout << l.get(key) << endl; } else if (command == "set") { int key, value; cin >> key >> value; l.set(key, value); } } return 0; }