#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <set>
#include <cassert>
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<int,Node*> 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
   virtual void set(int, int) = 0; //set function
   virtual int get(int) = 0; //get function

};
class LRUCache: public Cache{
    private:
    int count;
    public:
    LRUCache(int cp){
        this->cp=cp;
        count=0;
    }
    ~LRUCache(){
        Node* temp=this->head;
        while(temp->next){
            if(temp->prev)
                delete temp->prev;
            temp=temp->next;
        }
        delete temp;
        mp.clear();
    }
    void set(int a,int b){
        if(!mp[a]){
            if(count==0){
            Node* n=new Node(a,b);
            mp[a]=n;
                tail=head=n;
            }else if(count<cp){
                Node* n=new Node(a,b);
                mp[a]=n;
                tail->next=n;
                Node* temp=tail;
                tail=tail->next;
                tail->prev=temp;
            }else{
                mp.erase(head->key);
                head->value=b;
                head->key=a;
                mp[head->key]=head;
            }
            count++;
        }else{
            Node* temp=mp[a];
            mp[tail->key]=temp;
            mp[a]=tail;
            temp->value=tail->value;
            temp->key=tail->key;
            tail->value=b;
            tail->key=a;
            
        }
        
    }
    int get(int key){
        return mp[key]?mp[key]->value:-1;
    }
    
};
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;
}

   return 0;
}