// First idea (O(QNlogN))
// build a segment tree, segment L to R has value LCA(a[L..R])
// for every query, fix left of subarray and binary search for R
// to get a vertex with depth equal to the required vertex, then compare
// this can be done as depth(LCA(a[L..R-1])) <= depth(LCA(a[L..R]))
// Main solution O(QlogN)
// In what condition does depth(LCA(a[L..R-1])) < depth(LCA(a[L..R])) occur?
// that is when a[R] is in a different subtree to a[L..R-1]
// notice that we can just consider one representative of a[L..R-1] and compare to a[R]
// lca(a[L..R]) = lca(a[R-1], a[R])
// maintain all consecutive pairs
#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;
#define ll long long
#define ld long double
const int MX = 200005;
const int LG = (int)log2(MX) + 2;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
#define gc getchar//_unlocked //can't for window server
void cin(int &x){
char c = gc(); bool neg = false;
for(; c < '0'||'9' < c; c = gc())
if(c == '-') neg=true;
x = c - '0'; c = gc();
for(; '0' <= c && c <= '9'; c = gc())
x = (x << 1) + (x << 3) + (c - '0');
if(neg) x = -x;
}
int n, m, q, a[MX];
vector<int> adj[MX];
set<int> ans_1[MX], ans_2[MX];
int anc[MX][LG], depth[MX];
void dfs(int nw, int bf){
anc[nw][0] = bf;
depth[nw] = depth[bf] + 1;
for(int nx : adj[nw]) if(nx != bf)
dfs(nx, nw);
}
void build_lca(){
for(int j = 1; j < LG; j ++)
for(int i = 1; i <= n; i ++)
anc[i][j] = anc[anc[i][j - 1]][j - 1];
}
int lca(int u, int v){
if(depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for(int i = LG - 1; i >= 0; i --)
if(diff & (1 << i)) u = anc[u][i];
if(u == v) return u;
for(int i = LG - 1; i >= 0; i --)
if(anc[u][i] != anc[v][i])
u = anc[u][i], v = anc[v][i];
return anc[u][0];
}
int main(){
cin(n); cin(m); cin(q);
for(int u, v, i = 1; i < n; i ++){
cin(u); cin(v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 1);
build_lca();
for(int i = 1; i <= m; i ++){
cin(a[i]);
ans_1[a[i]].insert(i);
}
for(int i = 1; i < m; i ++){
int lc = lca(a[i], a[i + 1]);
ans_2[lc].insert(i);
}
for(int tp, l, r, ps, v; q --;){
cin(tp);
if(tp == 1){
cin(ps); cin(v);
if(ps > 1){
int get = lca(a[ps - 1], a[ps]);
ans_2[get].erase(ans_2[get].find(ps - 1));
get = lca(a[ps - 1], v);
ans_2[get].insert(ps - 1);
}
if(ps < m){
int get = lca(a[ps], a[ps + 1]);
ans_2[get].erase(ans_2[get].find(ps));
get = lca(v, a[ps + 1]);
ans_2[get].insert(ps);
}
ans_1[a[ps]].erase(ans_1[a[ps]].find(ps));
a[ps] = v;
ans_1[a[ps]].insert(ps);
}else{
cin(l); cin(r); cin(v);
auto it = ans_2[v].lower_bound(l);
if(it != ans_2[v].end() && l <= *it && *it + 1 <= r)
printf("%d %d\n", *it, *it + 1);
else{
it = ans_1[v].lower_bound(l);
if(it != ans_1[v].end() && l <= *it && *it <= r)
printf("%d %d\n", *it, *it);
else
printf("-1 -1\n");
}
}
}
return 0;
}
