#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second
#define siz(v) (int)(v).size()
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define dbg(x) "[" #x " = " << x << "]"
using namespace std;
const int MAXN = 2e5 + 5, LOG = 19;
int numNode, numVal, numQuery, val[MAXN], h[MAXN];
int tour[MAXN << 1], rtour[MAXN], st[LOG][MAXN << 1];
set<int > pos[MAXN], node[MAXN];
vector<int > adj[MAXN];
void input(){
cin >> numNode >> numVal >> numQuery;
for(int i = 1; i < numNode; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 1; i <= numVal; i++){
cin >> val[i];
}
}
void dfsInit(int u, int par = 0){
tour[++tour[0]] = u;
rtour[u] = tour[0];
for(int v: adj[u]) if (v != par){
h[v] = h[u] + 1;
dfsInit(v, u);
tour[++tour[0]] = u;
}
}
#define minHeight(a, b) (h[a] < h[b] ? a: b)
void sparseTable(){
for(int i = 1; i <= tour[0]; i++) st[0][i] = tour[i];
for(int j = 1; j < LOG; j++)
for(int i = 1; i + MASK(j - 1) <= tour[0]; i++){
st[j][i] = minHeight(st[j - 1][i], st[j - 1][i + MASK(j - 1)]);
}
}
int lca(int u, int v){
int l = rtour[u], r = rtour[v];
if (l > r) swap(l, r);
int k = __lg(r - l + 1);
return minHeight(st[k][l], st[k][r - MASK(k) + 1]);
}
void del(const int &id){
if (id > 1) pos[lca(val[id - 1], val[id])].erase(id - 1);
if (id < numVal) pos[lca(val[id + 1], val[id])].erase(id);
}
void add(const int &id){
if (id > 1) pos[lca(val[id - 1], val[id])].insert(id - 1);
if (id < numVal) pos[lca(val[id + 1], val[id])].insert(id);
}
void solve(){
dfsInit(1);
sparseTable();
for(int i = 1; i < numVal; i++){
node[val[i]].insert(i);
add(i);
}
node[val[numVal]].insert(numVal);
for(int q = 1; q <= numQuery; q++){
int type; cin >> type;
if (type == 1){
int id, v; cin >> id >> v;
del(id);
node[val[id]].erase(id);
val[id] = v;
node[val[id]].insert(id);
add(id);
}else{
int l, r, v; cin >> l >> r >> v;
set<int >::iterator it = pos[v].lower_bound(l), it2 = node[v].lower_bound(l);
if ((it2 != end(node[v]) && *it2 <= r) && (it != end(pos[v]) && *it < r)){
if (*it + 1 >= *it2){
cout << *it2 << ' ' << *it2 << '\n';
}else{
cout << *it << ' ' << *it + 1 << '\n';
}
}else if (it2 != end(node[v]) && *it2 <= r){
cout << *it2 << ' ' << *it2 << '\n';
}else if (it != end(pos[v]) && *it < r){
cout << *it << ' ' << *it + 1 << '\n';
}else{
cout << -1 << ' ' << -1 << '\n';
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int t = 1;
// cin >> t;
while(t--){
input();
solve();
}
cerr << (1.0 * clock()) / CLOCKS_PER_SEC << ".s\n";
}
