rt……

# include <bits/stdc++.h>

# define int long long
# define up(i ,x ,y) for (int i = x ; i <= y ; i ++)
# define dn(i ,x ,y) for (int i = x ; i >= y ; i --)
# define inf 1e18

using namespace std;

inline int read (){int s = 0 ; bool w = 0 ; char c = getchar () ; while (!isdigit (c)) {w |= (c == '-') ,c = getchar () ;} while (isdigit (c)){s = (s << 1) + (s << 3) + (c ^ 48) ; c = getchar ();}return w ? -s : s;}
inline void write (int x){if (x < 0) putchar ('-') ,x = -x; if (x > 9) write (x / 10) ; putchar (x % 10 | 48);}
inline void writesp (int x){write (x) ,putchar (' ');}
inline void writeln (int x){write (x) ,putchar ('\n');}

const int N = 1e6 + 10;
int n ,m ,fa[N] ,dis[N] ,lc[N] ,rc[N] ,rt[N] ,v[N];

inline void pushup (int x){
  if (!x) return;
  if (dis[lc[x]] < dis[rc[x]]) swap (lc[x] ,rc[x]);
  if (dis[x] != dis[rc[x]] + 1) {
    dis[x] = dis[rc[x]] + 1;
    pushup (fa[x]);
  }  
} inline int merge (int x ,int y){
  if (!x || !y) return x | y;
  if ((v[x] == v[y] && x > y) || v[x] > v[y]) swap (x ,y);
  rc[x] = merge (rc[x] ,y);
  if (dis[lc[x]] < dis[rc[x]]) swap (lc[x] ,rc[x]);
  dis[x] = dis[rc[x]] + 1;
  return fa[lc[x]] = fa[rc[x]] = fa[x] = x;
} inline int del (int x ,int heap){
  int y = merge (lc[x] ,rc[x]);
  if (fa[x] == x) rt[heap] = fa[y] = y;
  else {
    fa[y] = fa[x];
    if (lc[fa[y]] == y) lc[fa[y]] = y;
    if (rc[fa[y]] == y) rc[fa[y]] = y;
    pushup (fa[y]);
  } lc[x] = rc[x] = 0;
  return heap;
} signed main (){
  n = read () ,m = read ();
  up (i ,1 ,n) v[i] = read () ,rt[i] = fa[i] = i ,dis[i] = 1;
  up (i ,1 ,m){
    int op = read ();
    if (op == 0){
      int x = read () ,y = read ();
      del (y ,x);
    } else if (op == 2){
      int x = read () ,y = read ();
      rt[x] = rt[y] = merge (x ,y);
    } else if (op == 1) {
      int x = read ();
      writeln (v[rt[x]]);
    } else {
      int x = read () ,y = read () ,z = read ();
      del (y ,x) ,v[y] = z ,lc[y] = rc[y] = dis[y] = 0 ,fa[y] = y ,rt[x] = rt[y] = merge (rt[x] ,y);
    }
  }
  return 0;

}