import java.util.*;

public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    class DNode{
        DNode next;
        DNode prev;
        int val;
        int key;
        public DNode(int val){
            this.val = val;
        }
        
        public DNode(int key, int val){
            this.key = key;
            this.val = val;
        }
    }
    
    public Solution(){
        head = new DNode(0);
        tail = new DNode(0);
        head.next = tail;
        tail.next = head;
        size = 0;
        map = new HashMap<>();
    }
    
    DNode head;
    DNode tail;
    int size;
    Map<Integer, DNode> map;
    int capacity;
    
    private void set(int key, int val){
        if (map.containsKey(key)){
            DNode node = map.get(key);
            node.val = val;
            delete(node);
            moveToFirst(node);
        }else{
            if(size == capacity){
                DNode last = tail.prev;
                delete(last);
                map.remove(last.key);
                size--;
            }
            DNode node = new DNode(key, val);
            map.put(key, node);
            size++;
            moveToFirst(node);
        }
    }
    
    private int get(int key){
        if (map.containsKey(key)){
            DNode node = map.get(key);
            delete(node);
            moveToFirst(node);
            return node.val;
        }else{
            return -1;
        }
    }
    
    private void delete(DNode node){
        DNode prev = node.prev;
        DNode next = node.next;
        prev.next = next;
        next.prev = prev;
    }
    
    private void moveToFirst(DNode node){
        DNode next = head.next;
        head.next = node;
        node.next = next;
        next.prev = node;
        node.prev = head;
    }
    
    public int[] LRU (int[][] operators, int k) {
        // write code here
        capacity = k;
        List<Integer> ans = new ArrayList<>();
        for (int[] operator : operators){
            if (operator[0] == 1){
                set(operator[1], operator[2]);
            }else{
                int temp = get(operator[1]);
                ans.add(temp);
            }
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}