#include <bits/stdc++.h>
using namespace std;
vector <int> adiacenta[200001];
int sir[200001] , inceput[200001] , adancime[200001] , tabel[19][400000];
multiset <int> gasit[10];
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; }
}
}
void Update (const int nod , const int stanga , const int dreapta , const int indice , const int valoare , const bool tip)
{
if (tip) { gasit[nod].insert(valoare); }
else { gasit[nod].erase(gasit[nod].find(valoare)); }
if (indice > 0 && stanga == dreapta)
{ return; }
const int mijloc = (stanga + dreapta) >> 1;
if (indice < 0 && -indice == mijloc)
{ return; }
if (abs(indice) <= mijloc) { Update(nod + 1 , stanga , mijloc , indice , valoare , tip); }
else { Update(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta , indice , valoare , tip); }
}
pair <int , int> Query (const int nod , const int stanga , const int dreapta , const int stanga_query , const int dreapta_query , const int dorit)
{
if (dreapta_query < stanga || dreapta < stanga_query || gasit[nod].find(dorit) == gasit[nod].end())
{ return {-1 , -1}; }
if (stanga == dreapta)
{ return {stanga , dreapta}; }
const int mijloc = (stanga + dreapta) >> 1;
if (stanga_query <= mijloc && mijloc + 1 <= dreapta_query && LCA(sir[mijloc] , sir[mijloc + 1]) == dorit)
{ return {mijloc , mijloc + 1}; }
const pair <int , int> candidat = Query(nod + 1 , stanga , mijloc , stanga_query , dreapta_query , dorit);
if (candidat.first == -1)
{ return Query(nod + ((mijloc - stanga + 1) << 1) , mijloc + 1 , dreapta , stanga_query , dreapta_query , dorit); }
return candidat;
}
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]; Update(1 , 1 , lungime , indice , sir[indice] , true); }
for (int indice = 1 ; indice < lungime ; indice++)
{ Update(1 , 1 , lungime , -indice , LCA(sir[indice] , sir[indice + 1]) , true); }
while (numar_operatii--)
{
int tip;
cin >> tip;
if (tip == 1)
{
int indice;
cin >> indice;
Update(1 , 1 , lungime , indice , sir[indice] , false);
if (indice > 1) { Update(1 , 1 , lungime , -(indice - 1) , LCA(sir[indice - 1] , sir[indice]) , false); }
if (indice < lungime) { Update(1 , 1 , lungime , -indice , LCA(sir[indice] , sir[indice + 1]) , false); }
cin >> sir[indice];
Update(1 , 1 , lungime , indice , sir[indice] , true);
if (indice > 1) { Update(1 , 1 , lungime , -(indice - 1) , LCA(sir[indice - 1] , sir[indice]) , true); }
if (indice < lungime) { Update(1 , 1 , lungime , -indice , LCA(sir[indice] , sir[indice + 1]) , true); }
}
else
{
int stanga , dreapta , dorit;
cin >> stanga >> dreapta >> dorit;
const pair <int , int> rezultat = Query(1 , 1 , lungime , stanga , dreapta , dorit);
cout << rezultat.first << ' ' << rezultat.second << '\n';
}
}
return 0;
}
