#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
ll minFreq=0;
unordered_map<ll,pair<ll,ll>> keyVal;
unordered_map<ll,list<ll>> freqList;
unordered_map<ll,list<ll>::iterator> pos;
ll get(ll key) 
{
    if(keyVal.find(key) == keyVal.end()) return -1;
    freqList[keyVal[key].second].erase(pos[key]);
    keyVal[key].second++;
    freqList[keyVal[key].second].push_back(key);
    pos[key] = --freqList[keyVal[key].second].end();
    if(freqList[minFreq].empty()) minFreq++;
    return keyVal[key].first;
}
void put(ll key, ll value) 
{
    if(!n) return;
    if(keyVal.find(key) != keyVal.end()) 
    {
        keyVal[key].first = value;
        freqList[keyVal[key].second].erase(pos[key]);
        keyVal[key].second++;
        freqList[keyVal[key].second].push_back(key);
        pos[key] = --freqList[keyVal[key].second].end();
        if(freqList[minFreq].empty())
            minFreq++;
        return;
    }
    if(keyVal.size()==n) 
    {
        ll delKey = freqList[minFreq].front();
        keyVal.erase(delKey);
        pos.erase(delKey);
        freqList[minFreq].pop_front();
    }
    keyVal[key] = {value,1};
    freqList[1].push_back(key);
    pos[key] = --freqList[1].end();
    minFreq = 1;
}
signed main() 
{
    cin>>n;
    ll q; cin>>q;
    while(q--)
    {
        ll x,y,z; cin>>x>>y>>z;
        if(x==1) cout<<get(y)<<" ";
        else put(y,z);
    }
    return 0;
}

WITH june_events AS (
  SELECT *
  FROM events
  WHERE dt >= '2022-06-01' AND dt < '2022-07-01'
),
grouped_data AS (
  SELECT 
    mime,
    GROUP_CONCAT(DISTINCT SUBSTRING_INDEX(filename, '.', -1) ORDER BY SUBSTRING_INDEX(filename, '.', -1) SEPARATOR ', ') AS extension,
    COUNT(*) AS files,
    SUM(filesize) / (1024 * 1024) AS total_mib
  FROM june_events
  GROUP BY mime
)
SELECT 
  mime,
  extension,
  files,
  CASE 
    WHEN total_mib >= 1024 THEN CONCAT(ROUND(total_mib / 1024, 2), ' GiB')
    ELSE CONCAT(ROUND(total_mib, 2), ' MiB')
  END AS total
FROM grouped_data
ORDER BY total_mib DESC;

def inject_in_case(s, k):
    for i in range(len(s)):
        if k >= s[i]:
            return s[:i] + k + s[i:]
    return s + k
s = input().strip()
k = input().strip()

if len(k) == 1:
    result = inject_in_case(s, k)
    print(result)

vector < vector < int > > adj;
    string letters;

    int dfs(int u, int p, int& best_path){
        // visit the current node
        int best_path_1 = 0, best_path_2 = 0;
        
        auto update_max = [&](int x){
            if(x >= best_path_1)
                best_path_2 = best_path_1, best_path_1 = x;
            else if(x >= best_path_2)
                best_path_2 = x; 
        };

        for(auto& v : adj[u]){
            // if the adjacent node not visited and not the same letter let's calc it
            if(v == p) continue;
            int v_ans = dfs(v, u, best_path);
            if(letters[u] != letters[v])
                update_max(v_ans);
        }

        // take two branches
        best_path = max({best_path, best_path_1 + best_path_2 + 1});

        // the maximum path from the current node
        return 1 + best_path_1;
    }

    void add_edge(int u, int v){
        adj[u].push_back(v), adj[v].push_back(u);
    }

    int longestPath(vector<int>& parent, string& s) {
        // global variable initialization
        int n = parent.size();
        adj = vector < vector < int > > (n);
        letters = s;

        // add edges between i and parent of i
        for(int i = 1; i < n; i++)
            add_edge(i, parent[i]);
        
        int best_path = 0;
        dfs(0, -1, best_path);

        // the length of the longest path with the required conditions.
        return best_path;
    }


int main()
{
int n; cin >> n;
vector<int> parent(n);
for (auto & x : parent) cin >> x;
string s; cin >> s;
cout << longestPath(parent,  s) << endl;
}

class Solution { 
    int ring_size; 
    unordered_map<char,vector<int>> mp; 
    int clockwise(int curr, int new_pos){ 
        if(new_pos >= curr){ 
            return new_pos-curr; 
        } 
        return ring_size - (curr - new_pos); 
    } 
    int anti_clockwise(int curr, int new_pos){ 
        if(curr >= new_pos){ 
            return curr - new_pos; 
        } 
        return ring_size - (new_pos - curr); 
    } 
    int solve(string &key, int idx, int pos, vector<vector<int>>& dp){ 
        if(idx == key.size()){ 
            return 0; //end of key 
        } 
        if(dp[idx][pos] != -1){ 
            return dp[idx][pos]; 
        } 
        int steps = INT_MAX; 
        int key_value = key[idx]; 
         
        //going to all indexes 
        for(int i = 0; i < mp[key_value].size(); i++){ 
            int new_pos = mp[key_value][i]; 
            int taken = solve(key,idx+1,new_pos,dp); 
            //clockwise 
            steps = min(steps,1+clockwise(pos,new_pos)+taken); 
            //anticlockwise 
            steps = min(steps,1+anti_clockwise(pos,new_pos)+taken); 
        } 
        return dp[idx][pos] = steps; 
    } 
public: 
    int findRotateSteps(string& ring, string& key) { 
        ring_size = ring.size(); 
        for(int i = 0; i < ring_size; i++){ 
            mp[ring[i]].push_back(i);  
        } 

        vector<vector<int>> dp(key.size(),vector<int>(ring.size(),-1)); 
        return solve(key,0,0,dp); 
    } 
};