ac

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * key 增删
 * 1. 新增key capacity满了才会需要删除key
 * 2. 访问 或 修改key，只需要增加出现频率，不涉及key的删除问题
 *
 * 关于最小频率：
 * 1. 新增key，那么显然最小频率是1
 * 2. 访问 或 修改key 导致频率发生变化，需要更新最小频率
 *
 * 结论：
 * 1. 新增key，需要重置最小频率为1
 * 2. 访问或修改key，重置val，调整最小频率
 */
class LfuMap{
    // 最大容量
    int capacity;

    // 有效的key
    HashMap<Integer, KeyInfo> keyValMap;

    // 出现次数 与 key的映射, 双向链表头部就是最久的要删除的
    HashMap<Integer, LinkedList<Integer>> frequentlyKeyMap;

    int minFrequent;

    public LfuMap(int size) {
        capacity = size;
        minFrequent = -1;
        keyValMap = new HashMap<>();
        frequentlyKeyMap = new HashMap<>();
    }

    public void set(int key, int val){
        if(keyValMap.isEmpty()){
            KeyInfo keyInfo = new KeyInfo(val, 1);
            keyValMap.put(key, keyInfo);

            minFrequent = 1;

            LinkedList<Integer> linkedList = new LinkedList<>();
            linkedList.addFirst(key);
            frequentlyKeyMap.put(1, linkedList);
        }else {
            // 原来出现过的key，此次cnt要加1
            if(keyValMap.containsKey(key)){
                // 更新值和频率，借用了一下get方法
                get(key);
                KeyInfo keyInfo = keyValMap.get(key);
                keyInfo.value = val;
                keyValMap.put(key, keyInfo);
            }else {
                // 新增的key
                // 需要先判断是不是满了
                if(keyValMap.size() == capacity) {
                    // 删除最小出现的，且是最早的那个key
                    Integer removeKey = frequentlyKeyMap.get(minFrequent).removeFirst();
                    keyValMap.remove(removeKey);
                }
                KeyInfo keyInfo = new KeyInfo(val,1);
                // 1。 新增key
                keyValMap.put(key, keyInfo);
                // 2。频率列表改变
                LinkedList<Integer> linkedList;
                if(frequentlyKeyMap.containsKey(1)){
                   linkedList = frequentlyKeyMap.get(1);
                }else {
                   linkedList = new LinkedList<>();
                }
                linkedList.addLast(key);
                // 3. 最小次数更新
                minFrequent = 1;
            }
        }
    }

    public int get(int key){
        if(keyValMap.containsKey(key)){
            // 原来就存在, 那么此次出现的次数肯定要加1
            KeyInfo keyInfo = keyValMap.get(key);
            int val = keyInfo.value;
            int oldFrequent = keyInfo.frequent;
            Integer linkedKey = key;

            // 1. occurCntKeyMap 的 oldOccurCnt 的链表要删除 linkedKey
            frequentlyKeyMap.get(oldFrequent).remove(linkedKey);
            if( frequentlyKeyMap.get(oldFrequent).isEmpty()){
                // 因为最小次数是由于这次新访问导致的
                minFrequent ++;
            }
            // 2. occurCntKeyMap 的 oldOccurCnt + 1 的链表尾部新增元素
            KeyInfo keyInfo1 = new KeyInfo(val, oldFrequent + 1);
            if(frequentlyKeyMap.containsKey(keyInfo1.frequent)){
                LinkedList<Integer> linkedList = frequentlyKeyMap.get(keyInfo1.frequent);
                linkedList.addLast(linkedKey);
                frequentlyKeyMap.put(keyInfo1.frequent, linkedList);
            }else {
                LinkedList<Integer> linkedList = new LinkedList<>();
                linkedList.addLast(linkedKey);
                frequentlyKeyMap.put(keyInfo1.frequent, linkedList);
            }
            // 3. 更新keyInfo
            keyValMap.put(key, keyInfo1);
            return val;
        }
        return -1;
    }


    class KeyInfo{
        public int value; // 值
        public int frequent; // 当前频率
        public KeyInfo(int value, int frequent) {
            this.value = value;
            this.frequent = frequent;
        }
    }
}

public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int n = sc.nextInt();
        int k = sc.nextInt();
        LfuMap lruMap = new LfuMap(k);
        for (int i = 0; i < n; i++) {
            int op = sc.nextInt();
            if(op == 1){
                // set
                int key = sc.nextInt();
                int val = sc.nextInt();
                lruMap.set(key, val);
            }
            if(op == 2){
                // get
                int key = sc.nextInt();
                System.out.println(lruMap.get(key));
            }
        }
    }

}
/*
8 3
1 1 1
1 2 2
1 3 2
1 2 4
1 3 5
2 2
1 4 4
2 1

4
-1
 */