#include <bits/stdc++.h>
#define NMAX 200001
#define LOG 20
using namespace std;
int n, m, q;
vector<int> muchii[NMAX]; ///muchiile arborelui
int nivel[NMAX]; ///nivelul fiecarui nod
int stra[LOG][NMAX]; ///stra[e][i] = al e-lea stramos al nodului i
void dfs(int nod, int tata) ///salvam tatal fiecarui nod
{
stra[0][nod]=tata;
nivel[nod]=1+nivel[tata];
for(auto& fiu : muchii[nod])
{
if(fiu!=tata) dfs(fiu, nod);
}
}
void precalc() ///precalculam structura de date stra
{
for(int e=1; e<LOG; e++)
{
for(int i=1; i<=n; i++)
stra[e][i]=stra[e-1][stra[e-1][i]];
}
}
int up(int nod, int k) ///al k-lea stramos al lui nod
{
for(int e=LOG-1; e>=0; e--)
{
if((1<<e)<=k)
{
nod=stra[e][nod];
k-=(1<<e);
}
}
return nod;
}
int LCA(int nod1, int nod2) ///LCA-ul a doua noduri
{
if(nivel[nod1]<nivel[nod2]) swap(nod1, nod2);
if(nod2==0) return nod1;
nod1=up(nod1, nivel[nod1]-nivel[nod2]); ///il aducem pe nod1 la nivelul nodului nod2
if(nod1==nod2) return nod1;
for(int e=LOG-1; e>=0; e--) ///cautam binar ultimul stramos al fiecarui nod care nu este comun
{
if(stra[e][nod1]!=stra[e][nod2])
{
nod1=stra[e][nod1];
nod2=stra[e][nod2];
}
}
return stra[0][nod1];
}
int a[NMAX];
int lca_a[NMAX]; ///LCA-ul a doua numere situate pe pozitii consecutive in a
set<int> pozitii_a[NMAX]; ///pozitiile pe care se afla fiecare valoare in a
set<int> pozitii_lca[NMAX]; ///pozitiile pe care se afla fiecare valoare in lca_a
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
for(int i=1; i<=n-1; i++)
{
int u, v;
cin >> u >> v;
muchii[u].push_back(v);
muchii[v].push_back(u);
}
dfs(1, 0);
precalc();
for(int i=1; i<=m; i++)
{
cin >> a[i];
pozitii_a[a[i]].insert(i);
}
for(int i=1; i<=m; i++)
{
///daca exista un interval in [l, r] care are LCA-ul v, atunci fie exista doua pozitii consecutive cu LCA-ul v, fie v se afla in interval
///astfel, avem nevoie doar de LCA-ul numerelor aflate pe pozitii consecutive
lca_a[i]=LCA(a[i], a[i+1]);
pozitii_lca[lca_a[i]].insert(i);
}
while(q--)
{
int tip;
cin >> tip;
if(tip==1)
{
int pos, v;
cin >> pos >> v;
pozitii_a[a[pos]].erase(pos);
if(pos>1) pozitii_lca[lca_a[pos-1]].erase(pos-1);
pozitii_lca[lca_a[pos]].erase(pos);
a[pos]=v;
if(pos>1) lca_a[pos-1]=LCA(a[pos-1], a[pos]);
lca_a[pos]=LCA(a[pos], a[pos+1]);
pozitii_a[a[pos]].insert(pos);
if(pos>1) pozitii_lca[lca_a[pos-1]].insert(pos-1);
pozitii_lca[lca_a[pos]].insert(pos);
}
else
{
int l, r, v;
cin >> l >> r >> v;
if(pozitii_a[v].lower_bound(l)!=pozitii_a[v].end() && (*pozitii_a[v].lower_bound(l))<=r) ///cautam prima pozitie a lui v situata dupa l; daca aceasta este mai mica sau egala cu r, atunci luam intervalul [x, x]
{
int x=(*pozitii_a[v].lower_bound(l));
cout << x << " " << x << "\n";
}
else if(pozitii_lca[v].lower_bound(l)!=pozitii_lca[v].end() && (*pozitii_lca[v].lower_bound(l))<=r-1) ///cautam prima pozitie a lui v ca LCA situata dupa l; daca aceasta este mai mica sau egala cu r-1, atunci luam intervalul [x, x+1]
{
int x=(*pozitii_lca[v].lower_bound(l));
cout << x << " " << x+1 << "\n";
}
else
{
cout << -1 << " " << -1 << "\n";
}
}
}
return 0;
}
