#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    int L, R;       // segment range (0-indexed)
    int left, right; // indices of children in the tree vector (-1 if leaf)
    int dp[2];      // dp[0] if starting with minimizer, dp[1] if starting with maximizer
};
 
int N; // size of the array
vector<int> A; // the array (0-indexed)
vector<Node> tree; // our game tree

// Build the tree for segment [l, r] (0-indexed)
// Returns the index of the node in the tree vector.
int buildTree(int l, int r) {
    int idx = tree.size();
    tree.push_back({l, r, -1, -1, {0, 0}});
    if(l == r) {
        tree[idx].dp[0] = A[l];
        tree[idx].dp[1] = A[l];
        return idx;
    }
    int len = r - l + 1;
    int leftSize = len / 2;  // floor division
    int leftL = l, leftR = l + leftSize - 1;
    int rightL = l + leftSize, rightR = r;
    int leftIdx = buildTree(leftL, leftR);
    int rightIdx = buildTree(rightL, rightR);
    tree[idx].left = leftIdx;
    tree[idx].right = rightIdx;
    // Combine children: note the turn switches for the remaining segment.
    tree[idx].dp[0] = min(tree[leftIdx].dp[1], tree[rightIdx].dp[1]);
    tree[idx].dp[1] = max(tree[leftIdx].dp[0], tree[rightIdx].dp[0]);
    return idx;
}
 
// Update the tree: update position pos (0-indexed) to new value 'val'
void updateTree(int idx, int pos, int val) {
    Node &node = tree[idx];
    if(pos < node.L || pos > node.R) return;
    if(node.L == node.R) {
        node.dp[0] = val;
        node.dp[1] = val;
        return;
    }
    // Recurse to children.
    updateTree(tree[idx].left, pos, val);
    updateTree(tree[idx].right, pos, val);
    // Recompute current node's dp values.
    node.dp[0] = min(tree[node.left].dp[1], tree[node.right].dp[1]);
    node.dp[1] = max(tree[node.left].dp[0], tree[node.right].dp[0]);
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int Q;
    cin >> N >> Q;
    A.resize(N);
    for (int i = 0; i < N; i++){
        cin >> A[i];
    }
    
    // Build the game tree over the whole array [0, N-1].
    tree.reserve(2 * N);  // worst-case size is O(N)
    int root = buildTree(0, N-1);
    
    // Process queries.
    // Each query is given as: i v p 
    // where 1<=i<=N; update A[i-1] to v and then, if p==0 then Thakur (minimizer) starts, 
    // if p==1 then Roy (maximizer) starts.
    while(Q--){
        int i, v, p;
        cin >> i >> v >> p;
        i--; // convert to 0-indexed
        // Update the array and the game tree.
        A[i] = v;
        updateTree(root, i, v);
        // Answer is stored in tree[root].dp[p]
        cout << tree[root].dp[p] << "\n";
    }
    
    return 0;
}