#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <numeric>
#include <cassert>

using namespace std;

#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(...) DBG2::cprint(#__VA_ARGS__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(...)
#endif

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

using llong = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using II = pair<int,int>;

class SegmentTree {
   struct Node {
      int min_val, max_val;
      Node(int x = 0) : min_val(x), max_val(x) {
      }
      Node operator+(Node& r) const {
         Node ret;
         ret.min_val = min( this->max_val, r.max_val );
         ret.max_val = max( this->min_val, r.min_val );
         return ret;
      }
   };

   int N;
   vector<Node> tree;

   void _build(const vector<int>& A, int node, int L, int R) {
      if (L == R) {
         tree[node] = Node(A[L]);
         return;
      }

      _build(A, 2*node, L, (L+R)/2);
      _build(A, 2*node+1, (L+R)/2+1, R);

      tree[node] = tree[2*node] + tree[2*node+1];
   }
   void _update(int idx, int val, int node, int L, int R) {
      if (idx < L || idx > R)
         return;
      
      if (L == R) {
         tree[node] = Node(val);
         return;
      }

      _update(idx, val, 2*node, L, (L+R)/2);
      _update(idx, val, 2*node+1, (L+R)/2+1, R);

      tree[node] = tree[2*node] + tree[2*node+1];
   }

public:
   SegmentTree(const vector<int>& A) {
      N = A.size();
      int NUM_NODES = 4*N+1;
      tree = vector<Node>(NUM_NODES);
      _build(A, 1, 0, N-1);
   }

   void update(int idx, int val) {
      _update(idx, val, 1, 0, N-1);
   }

   int query(int p) {
      return p == 0 ? tree[1].min_val : tree[1].max_val;
   }

};


int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(nullptr);

   int N, Q;
   cin >> N >> Q;
   VI A(N);
   REP(i, N)
      cin >> A[i];

   SegmentTree st(A);
   FOR(q, 1, Q) {
      int i, v, p;
      cin >> i >> v >> p;
      --i;
      st.update(i, v);
      int res = st.query(p);
      cout << res << '\n';
   }

   return 0;
}