/*#include <iostream>
#include<vector>
using namespace std;

int minRastojanje(int V,int dist[], bool visited[])
{
	int min = 80001, min_index;

	for (int i = 0; i < V; i++)
		if (visited[i] == false && dist[i] <= min)
			{
				min = dist[i];
				min_index = i;
			}
	return min_index;
}

int najdalje(int l, int r, int x, int N, int mp[], int naselje[]){

	int dist[N],g,i,j,max=l;
	bool visited[N]; 
	for (int i = 0; i < N; i++)
		{
			dist[i] = 80001;
			visited[i] = false;
		}
	dist[x] = 0;
	for (i = 0; i < N - 1; i++) {
		
		int u = minRastojanje(N,dist, visited);
		visited[u] = true;
					for(g=mp[u];g<mp[u+1];g++){
							if (visited[mp[g]]== false && dist[u] != 800001 && dist[u] + 1 < dist[mp[g]])
						{
							dist[mp[g]] = dist[u] + 1;
						}
						
					}
					
			
					
		}
	for(i=0;i<N;i++)	
	{

			if(naselje[i]>=l&&naselje[i]<=r&&dist[i]>dist[max])
				{
					max=i;	
						
				}

		
		
	}
	return max;
}
	


int main()
{
	int a,b,N,Q,i,j,l,r,x;
	int start=0;
	cin>>N;
	int naselje[N];
	vector<int> grane[N];
	for(i=0;i<N;i++){
		cin>>naselje[i];
		naselje[i]--;
	}
	
	int mp[3*N-2];
	
	for(i=0;i<N-1;i++){
		cin>>a;
		cin>>b;
		grane[a-1].push_back(b-1);
		grane[b-1].push_back(a-1);
		
	}	
	for(i=0;i<N;i++){
		if(i==0){
			mp[0]=N;
		}
		else{
		mp[i]=mp[i-1]+grane[i-1].size();
		}
		for(j=0;j<grane[i].size();j++){
			mp[mp[i]+j]=grane[i].at(j);
		}
	}
	
	cin>>Q;
	int k=0;
	vector<int> ispis;
    int temp,vrsta;
	for(Q=Q;Q>0;Q--)
	{
		cin>>vrsta;
		if(vrsta==1){
			cin>>a>>b;
			temp=naselje[a-1];
			naselje[a-1]=naselje[b-1];
			naselje[b-1]=temp;
		}
		else{
			cin>>l>>r>>x;
					x--;			
			
			l--;
			r--;
			ispis.push_back(najdalje(l,r,x,N,mp,naselje));
		}
	}
	for(Q=0;Q<ispis.size();Q++)
		cout<<ispis.at(Q)<<endl;
	
	
	
	return 0;
}

*/

#include <iostream>
#include<vector>
using namespace std;

int minRastojanje(int V,int dist[], bool visited[])
{
	int min = 80001, min_index;

	for (int i = 0; i < V; i++)
		if (visited[i] == false && dist[i] <= min)
			{
				min = dist[i];
				min_index = i;
			}
	return min_index;
}

int najdalje(int l, int r, int x, int N, int mp[], int naselje[]){

	int dist[N],g,i,j,max=l;
	bool visited[N]; 
	for (int i = 0; i < N; i++)
		{
			dist[i] = 80001;
			visited[i] = false;
		}
	dist[x] = 0;
	for (i = 0; i < N - 1; i++) {
		
		int u = minRastojanje(N,dist, visited);
		visited[u] = true;
					for(g=mp[u];g<mp[u+1];g++){
							if (visited[mp[g]]== false && dist[u] != 800001 && dist[u] + 1 < dist[mp[g]])
						{
							dist[mp[g]] = dist[u] + 1;
						}
						
					}
					
			
					
		}
	for(i=0;i<N;i++)	
	{

			if(naselje[i]>=l&&naselje[i]<=r&&dist[i]>dist[max])
				{
					max=i;	
						
				}

		
		
	}
	return max;
}
	


int main()
{
	int a,b,N,Q,i,zi,zj,j,l,r,x;
	int start=0;
	cin>>N;
	int naselje[N];
	vector<int> grane[N];
	for(i=0;i<N;i++){
		cin>>naselje[i];
		naselje[i]--;
	}
	
	int mp[3*N-2];
	
	for(i=0;i<N-1;i++){
		cin>>a;
		cin>>b;
		grane[a-1].push_back(b-1);
		grane[b-1].push_back(a-1);
		
	}	
	for(i=0;i<N;i++){
		if(i==0){
			mp[0]=N;
		}
		else{
		mp[i]=mp[i-1]+grane[i-1].size();
		}
		for(j=0;j<grane[i].size();j++){
			mp[mp[i]+j]=grane[i].at(j);
		}
	}
	
	cin>>Q;
	vector<int> ispis;
    int temp,vrsta;
	for(Q=Q;Q>0;Q--)
	{
		cin>>vrsta;
		if(vrsta==1){
			cin>>a>>b;
			
			for(i=0;i<N;i++){
				if(naselje[i]==a-1)
					zi=i;
				if(naselje[i]==b-1)
					zj=i;
			}
			temp=naselje[zi];
			naselje[zi]=naselje[zj];
			naselje[zj]=temp;
		}
		else{
			cin>>l>>r>>x;
					x--;			
			
			l--;
			r--;
			ispis.push_back(najdalje(l,r,x,N,mp,naselje));
		}
	}
	for(Q=0;Q<ispis.size();Q++)
		cout<<ispis.at(Q)<<endl;
	
	
	
	return 0;
}