#include <bits/stdc++.h>

// #ifndef ONLINE_JUDGE
// #include "template.cpp"
// #else
// #define debug(...)
// #define debugArr(...)
// #endif

#define F first
#define S second
#define int long long
#define double long double
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define mp(x, y) make_pair(x, y)
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define INF (int)1e9
using namespace std;

using pii = pair<int, int>;
using pdd = pair<double, double>;
using pbb = pair<bool, bool>;
using pcc = pair<char, char>;
using pss = pair<string, string>;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vpii = vector<pair<int, int>>;
using vpdd = vector<pair<double, double>>;
using vpbb = vector<pair<bool, bool>>;
using vpcc = vector<pair<char, char>>;
using vpss = vector<pair<string, string>>;
using vvi = vector<vector<int>>;
using vvd = vector<vector<double>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvs = vector<vector<string>>;
using vvpii = vector<vector<pair<int, int>>>;
using vvpdd = vector<vector<pair<double, double>>>;
using vvpbb = vector<vector<pair<bool, bool>>>;
using vvpcc = vector<vector<pair<char, char>>>;
using vvpss = vector<vector<pair<string, string>>>;

// clang-format off
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T> T sqrt_(T elem) {int l=1,r=elem;while(l<=r){int mid=l+(r-l)/2LL;if(mid>elem/mid){r=mid-1;}else{int val=mid*mid;if(val<=elem){l=mid+1;}else{r=mid-1;}}}return r;}
template <class T> T ceil_(T a,T b) {return(a+b-1)/b;};
template <class T> T mod_add(T a,T b,T mod){return((a%mod)+(b%mod))% mod;}
template <class T> T mod_sub(T a,T b,T mod){return((a%mod)-(b%mod)+mod)%mod;}
template <class T> T mod_mul(T a,T b,T mod){return((a%mod)*(b%mod))%mod;}
template <class T> T mod_inv(T a,T mod){T m0=mod,y=0,x=1;if(mod==1)return 0;while(a>1){T q=a/mod;T t=mod;mod=a%mod,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=m0;return x;}
template <class T> T mod_div(T a,T b,T mod){return mod_mul(a,mod_inv(b,mod),mod);}
// clang-format on
void solve() {
  int n, k;
  cin >> n >> k;

  vi a(n + 1);

  vector<tuple<int, int, int>> b(k);

  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  for (auto &[x, y, z] : b) {
    cin >> x >> y >> z;
  }

  int m = __lg(n);

  vvpii seg(m + 4);
  map<tuple<int, int, int>, vector<tuple<int, int, int>>> adj;
  map<tuple<int, int, int>, tuple<int, int, int>> par;
  vi initLvl(n + 1);

  queue<tuple<int, int, int>> q;
  q.push({1, 1, n});
  par[{1, 1, n}] = {-1, -1, -1};
  // lvl, left, right;

  while (!q.empty()) {
    auto [lvl, l, r] = q.front();
    seg[lvl].eb(l, r);
    q.pop();

    int l1 = l, r1 = l + (((r - l + 1) / 2) - 1);
    int l2 = r1 + 1, r2 = r;

    if (r - l <= 0) {
      initLvl[r] = lvl;
      continue;
    }

    adj[{lvl, l, r}].push_back({lvl + 1, l1, r1});
    adj[{lvl, l, r}].push_back({lvl + 1, l2, r2});

    par[{lvl + 1, l1, r1}] = {lvl, l, r};
    par[{lvl + 1, l2, r2}] = {lvl, l, r};

    q.push({lvl + 1, l1, r1});
    q.push({lvl + 1, l2, r2});
  }

  vector<vvi> dp(n + 1, vvi(m + 4, vi(2)));
  int lastLvl = *max_element(all(initLvl));

  for (int i = lastLvl; i >= 1; i--) {
    for (const auto [x, y] : seg[i]) {
      if (!adj.count({i, x, y})) {
        dp[x][i][0] = dp[x][i][1] = a[x];
      } else {
        int u = 0, v = INF;
        for (const auto [lvl1, l1, r1] : adj[{i, x, y}]) {
          u = max(u, dp[l1][lvl1][1]);
          v = min(v, dp[l1][lvl1][0]);
        }
        dp[x][i][0] = u, dp[x][i][1] = v;
      }
    }
  }

  for (const auto [ind, val, p] : b) {
    a[ind] = val;
    dp[ind][initLvl[ind]][0] = dp[ind][initLvl[ind]][1] = a[ind];
    int currLvl = initLvl[ind], currL = ind, currR = ind;
    while (true) {
      auto [lvl, l, r] = par[{currLvl, currL, currR}];
      // debug(lvl, l, r, currLvl, currL, currR);
      if (l == -1) {
        break;
      }
      int u = 0, v = INF;
      for (const auto [lvl1, l1, r1] : adj[{lvl, l, r}]) {
        u = max(u, dp[l1][lvl1][1]);
        v = min(v, dp[l1][lvl1][0]);
      }

      dp[l][lvl][0] = u, dp[l][lvl][1] = v;
      currLvl = lvl, currL = l, currR = r;
    }
    cout << dp[1][1][!p] << '\n';
  }
  return;
}

signed main() {

  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int tt = 1, count = 1;
  // cin >> tt;
  while (tt--) {
    // cout << "Case #" << count << ": ";
    solve();
    ++count;
  }
  return 0;
}