#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 2147483646
#define inf 9223372036854775806
int n,Q;
struct Quick_sort_simulates_insertion_sort{
	int num;
	int id;
}a[10000];
bool cmp(Quick_sort_simulates_insertion_sort &A,Quick_sort_simulates_insertion_sort &B){
	if(A.num==B.num)return A.id<B.id;
	return A.num<B.num;
}
int main(){
	scanf("%d %d",&n,&Q);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i].num);
		a[i].id=i;
	} 
	sort(a,a+n,cmp);
	for(int i=0;i<n;i++)cout<<a[i].num<<" "<<a[i].id<<endl;
	for(int i=0;i<Q;i++){
		int t,a1,b1;
		scanf("%d",&t);
		if(t==2){
			scanf("%d",&a1);
			a1--;
			printf("%d\n",a[a1].num+1);
		}
		else{
			scanf("%d",&a1,&b1);
			a1--;
			a[a1].num=b1;
			for(int j=n;j>=2;j--)
				if(cmp(a[j],a[j-1])){
					Quick_sort_simulates_insertion_sort kkksc03=a[j];
					a[j]=a[j-1];
					a[j-1]=kkksc03;
				}
			for(int j=2;j<=n;j++)
				if(cmp(a[j],a[j-1])){
					Quick_sort_simulates_insertion_sort kkksc03=a[j];
					a[j]=a[j-1];
					a[j-1]=kkksc03;
				}
			}
	}
	return 0;
}