//#pragma GCC optomize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse4.1,sse4.2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define max_heap priority_queue<pair <ll, pair <ll, ll>>>
#define min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
#define sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout);
#define endl '\n'
#define md(a) (a % mod + mod) % mod
#define pb push_back
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//cout << setprecision(5) << fixed << f;
//hash prime = 769
ll const maxn = 2e5 + 123;
ll const inf = 3e18;
ll const loG = 23;
ll const mod = 1e9 + 7;
//ll const mod = 998244353;
ll const sq = 500;
ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}
int n, m, q, sz = 2, par[loG][maxn], h[maxn], arr[maxn], l, r, val;
vector <int> g[maxn];
vector <pair <int, int>> pak, add;
vector <set <pair <int, int>>> seg;
set <int> st[maxn];
void dfs(int v, int p){
h[v] = h[p] + 1;
par[0][v] = p;
for (int u : g[v]){
if (u != p)
dfs(u, v);
}
}
int jump(int v, int d){
for (int i = 0; i < loG; i++){
if ((1 << i) & d)
v = par[i][v];
}
return v;
}
int lca(int u, int v){
if (h[u] < h[v])
swap(u, v);
u = jump(u, h[u] - h[v]);
if(u == v) return u;
for(int i = loG - 1; i >= 0; i--)
if(par[i][u] != par[i][v])
u = par[i][u],
v = par[i][v];
return par[0][u];
}
void setter(int i, int x, int lx, int rx){
//cout << i << ' ' << x << ' ' << lx << ' ' << rx << " :" << endl;
//for (auto p : pak)
// cout << p.first << ' ' << p.second << endl;
//for (auto p : add)
// cout << p.first << ' ' << p.second << endl;
for (auto p : pak){
if (seg[x].find(p) != seg[x].end())
seg[x].erase(p);
}
if (rx - lx == 1){
for (auto p : add)
seg[x].insert(p);
return;
}
for (auto p : add)
seg[x].insert(p);
int mid = (lx + rx) / 2, a = 2 * x + 1, b = a + 1;
if (i < mid)
setter(i, a, lx, mid);
else
setter(i, b, mid, rx);
}
int getter(int x, int lx, int rx){
if (l >= rx || lx >= r){
return -1;
}
//cout << x << ' ' << lx << ' ' << rx << ' ' << val << endl;
//for (auto p : seg[x])
// cout << p.first << ' ' << p.second << endl;
//cout << endl;
if (l <= lx && rx <= r){
auto it = seg[x].upper_bound({val - 1, mod});
if (it != seg[x].end()){
auto p = *it;
if (p.first == val)
return p.second;
}
return -1;
}
int mid = (lx + rx) / 2, a = 2 * x + 1, b = a + 1;
int val1 = getter(a, lx, mid);
int val2 = getter(b, mid, rx);
return max(val1, val2);
}
void Solve(){
cin >> n >> m >> q;
while (sz <= m)
sz = sz * 2;
seg.resize(2 * sz);
for (int i = 1; i < n; i++){
int a, b; cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
dfs(1, 1);
for (int i = 1; i < loG; i++)
for (int j = 1; j < n + 1; j++)
par[i][j] = par[i - 1][par[i - 1][j]];
for (int i = 1; i < m + 1; i++){
cin >> arr[i];
st[arr[i]].insert(i);
}
for (int i = 1; i < m; i++){
int a = arr[i], b = arr[i + 1];
int c = lca(a, b);
add.clear();
add.pb({c, i});
setter(i, 0, 0, sz);
}
//cout << "OK?" << endl;
while (q--){
int c; cin >> c;
if (c == 1){
int i, x; cin >> i >> x;
add.clear();
pak.clear();
if (i > 1){
int a = arr[i - 1], b = arr[i], ah = lca(a, b);
pak.pb({ah, i - 1});
ah = lca(a, x);
add.pb({ah, i - 1});
setter(i - 1, 0, 0, sz);
}
add.clear();
pak.clear();
if (i < m){
int a = arr[i], b = arr[i + 1], ah = lca(a, b);
pak.pb({ah, i});
ah = lca(x, b);
add.pb({ah, i});
setter(i, 0, 0, sz);
}
st[arr[i]].erase(i);
arr[i] = x;
st[x].insert(i);
}
else{
cin >> l >> r >> val;
auto it = st[val].lower_bound(l);
if (it != st[val].end()){
int x = *it;
if (x <= r){
cout << x << ' ' << x << endl;
continue;
}
}
int ans = getter(0, 0, sz);
if (ans > 0){
cout << ans << ' ' << ans + 1 << endl;
}
else
cout << -1 << ' ' << -1 << endl;
}
}
}
int main(){
sariE;// filE;
int test = 1;
//cin >> test;
while (test--) Solve();
return 0;
}
