// 第三题AC代码
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String num = sc.nextLine();
        String[] nums = num.split(" ");
        int m = Integer.parseInt(nums[0]);
        int n = Integer.parseInt(nums[1]);
        HashMap<String, String> hashMap = new HashMap<>();
        LinkedList<String> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            String s = sc.nextLine();
            String[] ss = s.split(" ");
            if ("put".equals(ss[0])) {
                if (list.contains(ss[1])) {
                    list.remove(ss[1]);
                    hashMap.remove(ss[1]);
                } else if (hashMap.size() >= m) {
                    String first = list.removeFirst();
                    hashMap.remove(first);
                }
                list.add(ss[1]);
                hashMap.put(ss[1], ss[2]);
            } else {
                System.out.println(hashMap.get(ss[1]));
            }
        }
    }
}