#include <bits/stdc++.h>
using namespace std;
vector <int> adiacenta[200001];
int sir[200001] , inceput[200001] , adancime[200001] , tabel[19][400000];
set <int> locatie[200001][2];
inline int Combina (const int nod_1 , const int nod_2)
{
return adancime[nod_1] < adancime[nod_2] ? nod_1 : nod_2;
}
inline int LCA (const int nod_1 , const int nod_2)
{
const int stanga = min(inceput[nod_1] , inceput[nod_2]);
const int dreapta = max(inceput[nod_1] , inceput[nod_2]);
int exponent = 0;
while ((1 << (exponent + 1)) <= dreapta - stanga + 1)
{ exponent++; }
return Combina(tabel[exponent][stanga] , tabel[exponent][dreapta - (1 << exponent) + 1]);
}
void Parcurgere (const int nod , const int sursa)
{
adancime[nod] = adancime[sursa] + 1;
tabel[0][++tabel[0][0]] = nod;
inceput[nod] = tabel[0][0];
for (auto& vecin : adiacenta[nod]) {
if (vecin != sursa)
{ Parcurgere(vecin , nod); tabel[0][++tabel[0][0]] = nod; }
}
}
int main ()
{
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int numar_noduri , lungime , numar_operatii;
cin >> numar_noduri >> lungime >> numar_operatii;
for (int indice = 1 ; indice < numar_noduri ; indice++)
{
int nod[2]; cin >> nod[0] >> nod[1];
adiacenta[nod[0]].push_back(nod[1]);
adiacenta[nod[1]].push_back(nod[0]);
}
Parcurgere(1 , 0);
for (int exponent = 1 , putere = 2 ; putere <= tabel[0][0] ; exponent++ , putere <<= 1) {
for (int indice = 1 ; indice + putere - 1 <= tabel[0][0] ; indice++)
{ tabel[exponent][indice] = Combina(tabel[exponent - 1][indice] , tabel[exponent - 1][indice + (putere >> 1)]); }
}
for (int indice = 1 ; indice <= lungime ; indice++)
{ cin >> sir[indice]; locatie[sir[indice]][0].insert(indice); }
for (int indice = 1 ; indice < lungime ; indice++)
{ locatie[LCA(sir[indice] , sir[indice + 1])][1].insert(indice); }
while (numar_operatii--)
{
int tip;
cin >> tip;
if (tip == 1)
{
int indice;
cin >> indice;
locatie[sir[indice]][0].erase(indice);
if (indice > 1) { locatie[LCA(sir[indice - 1] , sir[indice])][1].erase(indice - 1); }
if (indice < lungime) { locatie[LCA(sir[indice] , sir[indice + 1])][1].erase(indice); }
cin >> sir[indice];
locatie[sir[indice]][0].insert(indice);
if (indice > 1) { locatie[LCA(sir[indice - 1] , sir[indice])][1].insert(indice - 1); }
if (indice < lungime) { locatie[LCA(sir[indice] , sir[indice + 1])][1].insert(indice); }
}
else
{
int stanga , dreapta , dorit;
cin >> stanga >> dreapta >> dorit;
auto candidat = locatie[dorit][0].lower_bound(stanga);
if (candidat != locatie[dorit][0].end() && *candidat <= dreapta)
{ cout << *candidat << ' ' << *candidat << '\n'; continue; }
candidat = locatie[dorit][1].lower_bound(stanga);
if (candidat != locatie[dorit][1].end() && *candidat < dreapta)
{ cout << *candidat << ' ' << *candidat + 1 << '\n'; continue; }
cout << "-1 -1\n";
}
}
return 0;
}
