#include<stdio.h>
#include<algorithm>

int main(){
	int N,Q;
	scanf("%d%d",&N,&Q);
	long long A[N];
	for(int i=0;i<N;i++){
		scanf("%lld",&A[i]);
	}
	for(;Q--;){
		int c;
		scanf("%d",&c);
		if(c==2){
			std::sort(A,A+N);
			continue;
		}
		if(c==3){
			int k;
			scanf("%d",&k);
			printf("%lld\n",A[k-1]);
			continue;
		}
		int k;long long x;
		scanf("%d%lld",&k,&x);
		A[k-1]=x;
	}
}