// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FOO(i,a,b) for(int i=(a);i<=int(b);++i)
#define OOF(i,a,b) for(int i=(a);i>=int(b);--i)
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;}
inline ll cdiv(ll x,ll m){return x/m+(x%m?(x<0)^(m>0):0);}
#ifdef OWO
#define safe cerr<<"\033[1;32m"<<__PRETTY_FUNCTION__<<" - "<<__LINE__<<" JIZZ\033[0m\n"
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
#else
#pragma GCC optimize("Ofast")
#define safe ((void)0)
#define debug(...) ((void)0)
#endif
const ll inf = 1e9, INF = 4e18;
const int N = 2e5 + 225, L = 19;
int n, m, q;
vector<int> adj[N];
int dep[N], anc[L][N];
void dfs(int u, int p = -1){
for(int v: adj[u])
if(v != p){
dep[v] = dep[u] + 1;
anc[0][v] = u;
dfs(v, u);
}
}
void makeLCA(){
FOO(l,1,L-1) FOO(i,1,n)
anc[l][i] = anc[l-1][anc[l-1][i]];
}
int LCA(int a, int b){
if(dep[a] < dep[b]) swap(a, b);
for(int d = dep[a] - dep[b], l = L - 1; l >= 0; --l)
if(d >> l & 1) a = anc[l][a];
if(a == b) return a;
for(int l = L - 1; l >= 0; --l)
if(anc[l][a] != anc[l][b]){
a = anc[l][a];
b = anc[l][b];
}
return anc[0][a];
}
int a[N];
set<int> pos[N], isl[N];
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m >> q;
FOR(_,n-1){
int u, v; cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
dfs(1);
makeLCA();
FOO(i,1,m){
cin >> a[i];
pos[a[i]].emplace(i);
}
auto add = [](int p){
pos[a[p]].emplace(p);
if(p > 1){
int lca = LCA(a[p-1], a[p]);
isl[lca].emplace(p-1);
}
if(p < m){
int lca = LCA(a[p], a[p+1]);
isl[lca].emplace(p);
}
};
auto rem = [](int p){
pos[a[p]].erase(p);
if(p > 1){
int lca = LCA(a[p-1], a[p]);
isl[lca].erase(p-1);
}
if(p < m){
int lca = LCA(a[p], a[p+1]);
isl[lca].erase(p);
}
};
FOO(i,1,m-1) add(i);
FOR(_,q){
int cmd; cin >> cmd;
if(cmd == 1){
int p, v; cin >> p >> v;
rem(p);
a[p] = v;
add(p);
} else {
int l, r, v; cin >> l >> r >> v;
auto it = isl[v].lower_bound(l);
if(it != end(isl[v]) and *it < r){
cout << *it << ' ' << (*it) + 1 << '\n';
} else {
it = pos[v].lower_bound(l);
int ans = -1;
if(it != end(pos[v]) and *it <= r)
ans = *it;
cout << ans << ' ' << ans << '\n';
}
}
}
return 0;
}
