#include <iostream>
#include <unordered_map>
#include <set>
#include <vector>
using namespace std;

vector<int> solve(int N, int Q, vector<vector<int>>& operations) {
    unordered_map<int, int> data; // Key-value mapping
    unordered_map<int, int> keyFreq; // Key-frequency mapping
    unordered_map<int, set<int>> freqKeys; // Frequency-keys mapping
    int minFreq = 0; // Minimum frequency

    vector<int> result;

    for (int i = 0; i < Q; i++) {
        int op = operations[i][0];
        int key = operations[i][1];

        if (op == 1) {
            if (data.find(key) == data.end()) {
                result.push_back(-1);
            } else {
                int freq = keyFreq[key];
                keyFreq[key] = freq + 1;
                freqKeys[freq].erase(key);
                freqKeys[freq + 1].insert(key);

                if (freqKeys[freq].empty() && freq == minFreq) {
                    minFreq++;
                }

                result.push_back(data[key]);
            }
        } else if (op == 2) {
            int value = operations[i][2];

            if (N == 0) {
                continue;
            }

            if (data.find(key) != data.end()) {
                data[key] = value;
                int freq = keyFreq[key];
                keyFreq[key] = freq + 1;
                freqKeys[freq].erase(key);
                freqKeys[freq + 1].insert(key);

                if (freqKeys[freq].empty() && freq == minFreq) {
                    minFreq++;
                }
            } else {
                if (data.size() >= N) {
                    int toRemove = *(freqKeys[minFreq].begin());
                    freqKeys[minFreq].erase(toRemove);
                    keyFreq.erase(toRemove);
                    data.erase(toRemove);
                }

                data[key] = value;
                keyFreq[key] = 1;
                freqKeys[1].insert(key);
                minFreq = 1;
            }
        }
    }

    return result;
}

int main() {
    int N = 3; // Capacity of the cache
    int Q = 6; // Number of operations
    vector<vector<int>> operations = {
        {2, 1, 1},
        {2, 2, 2},
        {2, 3, 3},
        {1, 1, -1},
        {2, 4, 4},
        {1, 2, 2}
    };

    vector<int> result = solve(N, Q, operations);

    for (int val : result) {
        cout << val << " ";
    }

    return 0;
}