#include <cstdio>

 #define DEBUG 1  // 调试开关
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
  char buf[MAXSIZE], *p1, *p2;
  char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
  IO() : p1(buf), p2(buf), pp(pbuf) {}

  ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
  char gc() {
#if DEBUG  // 调试，可显示字符
    return getchar();
#endif
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
    return p1 == p2 ? ' ' : *p1++;
  }

  bool blank(char ch) {
    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
  }

  template <class T>
  void read(T &x) {
    double tmp = 1;
    bool sign = false;
    x = 0;
    char ch = gc();
    for (; !isdigit(ch); ch = gc())
      if (ch == '-') sign = 1;
    for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
    if (ch == '.')
      for (ch = gc(); isdigit(ch); ch = gc())
        tmp /= 10.0, x += tmp * (ch - '0');
    if (sign) x = -x;
  }

  void read(char *s) {
    char ch = gc();
    for (; blank(ch); ch = gc());
    for (; !blank(ch); ch = gc()) *s++ = ch;
    *s = 0;
  }

  void read(char &c) { for (c = gc(); blank(c); c = gc()); }

  void push(const char &c) {
#if DEBUG  // 调试，可显示字符
    putchar(c);
#else
    if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
    *pp++ = c;
#endif
  }

  template <class T>
  void write(T x) {
    if (x < 0) x = -x, push('-');  // 负数输出
    static T sta[35];
    T top = 0;
    do {
      sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) push(sta[--top] + '0');
  }

  template <class T>
  void write(T x, char lastChar) {
    write(x), push(lastChar);
  }
} io;

const int MAXN = 3e4 + 10;
const int MAXV = 1e4;

int n, q;
int a[MAXN];
int fa[MAXN];

struct EDGE {
	int v, next;
	EDGE (){};
	EDGE (int v, int next) : v(v), next(next) {};
} edge[MAXN << 1];

int head[MAXN], edgeNum;
void AddEdge(int u, int v) {
	edge[++edgeNum] = EDGE(v, head[u]);
	head[u] = edgeNum;
}

struct ValueSegmentTree {
	struct NODE {
		int ls, rs;
		int sum;
	} node[MAXN * 20];
	int nodeNum, root[MAXN];
	int cnt;
	
	void Init() {
		for (int i = 1; i <= nodeNum; ++i) node[i].ls = node[i].rs = node[i].sum = 0;
		for (int i = 1; i <= cnt; ++i) root[i] = 0;
		nodeNum = 0;
		cnt = 0;
	}
	
	void Insert(int rootBefore, int &root, int lt, int rt, int x, int val) {
	    root = ++nodeNum;
	    node[root] = node[rootBefore];
	    if (lt == rt) {
	        node[root].sum += val;
	        return ;
	    }
	    int mid = lt + ((rt - lt) >> 1);
	    if (x <= mid) {
	        Insert(node[rootBefore].ls, node[root].ls, lt, mid, x, val);
	    } else {
	        Insert(node[rootBefore].rs, node[root].rs, mid + 1, rt, x, val);
	    }
	    node[root].sum = node[node[root].ls].sum + node[node[root].rs].sum;
	}
	
	int GetK(int rootBefore, int root, int lt, int rt, int k) {
	    if (lt == rt) {
	        return lt;
	    }
	    int mid = lt + ((rt - lt) >> 1);
	    int x = node[node[root].ls].sum - node[node[rootBefore].ls].sum;
	    if (x >= k) {
	        return GetK(node[rootBefore].ls, node[root].ls, lt, mid, k);
	    } else {
	        return GetK(node[rootBefore].rs, node[root].rs, mid + 1, rt, k - x);
	    }
	}
	
	void dfs(int now, int fa) {
		++cnt;
		Insert(root[cnt - 1], root[cnt], 1, MAXV, a[now], 1);
		for (int i = head[now]; i; i = edge[i].next) {
			if (edge[i].v == fa) continue;
			dfs(edge[i].v, now);
		}
	}
};

struct SegmentTree {
	struct node{
		int ls, rs;
		int sum;
	} node[MAXN * 20];
	int nodeNum, root;
	
	void Init() {
		for (int i = 1; i <= nodeNum; ++i) node[i].ls = node[i].rs = node[i].sum = 0;
		root = 0;
		nodeNum = 0;
	}
	
	void Insert(int &root, int lt, int rt, int x, int val) {
		if (!root) root = ++nodeNum;
		if (lt == rt) {
			node[root].sum += val;
			return ;
		}
		int mid = lt + ((rt - lt) >> 1);
		if (x <= mid) {
			Insert(node[root].ls, lt, mid, x, val);
		} else {
			Insert(node[root].rs, mid + 1, rt, x, val);
		}
		node[root].sum = node[node[root].ls].sum + node[node[root].rs].sum;
	}
	
	int GetSum(int root, int lt, int rt, int lq, int rq) {
		if (root == 0 || root > nodeNum) return 0;
		if (lt == lq && rt == rq) return node[root].sum;
		int mid = lt + ((rt - lt) >> 1);
		if (rq <= mid) {
			return GetSum(node[root].ls, lt, mid, lq, rq);
		} else if (lq > mid) {
			return GetSum(node[root].rs, mid + 1, rt, lq, rq);
		} else {
			return GetSum(node[root].ls, lt, mid, lq, mid) + GetSum(node[root].rs, mid + 1, rt, mid + 1, rq);
		}
	}
	
	void dfs(int now, int fa) {
		Insert(root, 1, MAXV, a[now], 1);
		for (int i = head[now]; i; i = edge[i].next) {
			if (edge[i].v == fa) continue;
			dfs(edge[i].v, now);
		}
	}
};

void dfs(int root, int fa) { // 找父亲
	::fa[root] = fa;
	for (int i = head[root]; i; i = edge[i].next) {
		if (edge[i].v == fa) continue;
		dfs(edge[i].v, root);
	}
}

ValueSegmentTree ST0, ST;
SegmentTree ST00, STT;

int main() {
	freopen("hjtree.in", "r", stdin);
	freopen("hjtree.out", "w", stdout);
	io.read(n);
	for (int i = 1; i <= n; ++i) {
		io.read(a[i]);
	}
	for (int i = 1; i <= n - 1; ++i) {
		int u, v;
		io.read(u), io.read(v);
		AddEdge(u, v);
		AddEdge(v, u);
	}
	
	dfs(1, 0);
	ST0.Init();
	ST0.dfs(1, 0);
	ST00.Init();
	ST00.dfs(1, 0);
	
	io.read(q);
	while (q--) {
		int opt, u, k, a, b, x;
		io.read(opt);
		if (opt == 1) {
			io.read(u), io.read(k);
			if (u == 1) {
				io.write(ST0.GetK(ST0.root[0], ST0.root[ST0.cnt], 1, MAXV, k), '\n');
			} else {
				ST.Init();
				ST.dfs(u, fa[u]);
				io.write(ST.GetK(ST.root[0], ST.root[ST.cnt], 1, MAXV, k), '\n');
			}
		} else if (opt == 2) {
			io.read(u), io.read(a), io.read(b);
			if (u == 1) {
				io.write(ST00.GetSum(ST00.root, 1, MAXV, a, b), '\n');
			} else {
				STT.Init();
				STT.dfs(u, fa[u]);
				io.write(STT.GetSum(STT.root, 1, MAXV, a, b), '\n');
			}
		} else {
			io.read(u), io.read(x);
			::a[u] = x;
			ST0.Init();
			ST00.Init();
			ST0.dfs(1, 0);
			ST00.dfs(1, 0);
		}
	}
	return 0;
}