#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
using namespace std;
vi ke[maxn];
set<int> s1[maxn],s2[maxn];
int n,m,a[maxn],q;
int h[maxn],par[maxn][20];
void dfs(int u,int parent)
{
for(int v : ke[u])
{
if(v == parent) continue;
h[v] = h[u] + 1;
par[v][0] = u;
dfs(v,u);
}
}
int lca(int u,int v)
{
if(h[u] < h[v]) swap(u,v);
int del = h[u] - h[v];
fod(i,19,0) if(bit(del,i)) u = par[u][i];
if(u == v) return u;
fod(i,19,0) if(par[u][i] != par[v][i])
{
u = par[u][i];
v = par[v][i];
}
return par[u][0];
}
main()
{
#define name "TASK"
if(fopen(name".inp","r"))
{
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> n >> m >> q;
fo(i,1,n - 1)
{
int u,v;
cin >> u >> v;
ke[u].pb(v);
ke[v].pb(u);
}
dfs(1,1);
fo(j,1,19) fo(i,1,n) par[i][j] = par[par[i][j - 1]][j - 1];
fo(i,1,m)
{
cin >> a[i];
s1[a[i]].insert(i);
}
fo(i,1,m - 1)
{
s2[lca(a[i],a[i + 1])].insert(i);
}
while(q--)
{
int type;
cin >> type;
if(type == 1)
{
int pos,v;
cin >> pos >> v;
auto lb = s1[a[pos]].lower_bound(pos);
s1[a[pos]].erase(lb);
s1[v].insert(pos);
if(pos > 1)
{
int _lca = lca(a[pos],a[pos - 1]);
lb = s2[_lca].lower_bound(pos - 1);
s2[_lca].erase(lb);
_lca = lca(v,a[pos - 1]);
s2[_lca].insert(pos - 1);
}
if(pos < m)
{
int _lca = lca(a[pos],a[pos + 1]);
lb = s2[_lca].lower_bound(pos);
s2[_lca].erase(lb);
_lca = lca(v,a[pos + 1]);
s2[_lca].insert(pos);
}
a[pos] = v;
}
else
{
int l,r,v;
cin >> l >> r >> v;
auto lb = s1[v].lower_bound(l);
if(lb != s1[v].end() and *lb >= l and *lb <= r) cout << *lb << ' ' << *lb << "\n";
else
{
lb = s2[v].lower_bound(l);
if(*lb >= l and *lb < r) cout << *lb << ' ' << *lb + 1 << "\n";
else cout << -1 << ' ' << -1 << "\n";
}
}
}
}
