#include <bits/stdc++.h>
using namespace std;
#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;
const int maxn = 200010;
vector<vi> p(19, vi(maxn, -1));
vi e[maxn];
vp t(maxn);
int tim;
void root(int x){
for (int i : e[x]){
if (p[0][x] == i) continue;
p[0][i] = x;
root(i);
}
}
void dfs(int x){
++tim;
int r = p[0][x];
for (int i = 1; i < 19 && r > -1; ++i){
p[i][x] = p[i - 1][r];
r = p[i - 1][r];
}
t[x].first = tim;
for (auto& i : e[x]){
dfs(i);
}
t[x].second = tim;
}
int ok(int x, int y){
if (t[x].first <= t[y].first && t[y].second <= t[x].second)
return x;
swap(x, y);
if (t[x].first <= t[y].first && t[y].second <= t[x].second)
return x;
return 0;
}
int lca(int x, int y){
int z = ok(x, y);
if (z){
return z;
}
for (int i = 18; i > -1; --i){
int tmp = p[i][x];
if (tmp == -1 || ok(tmp, y)) continue;
x = tmp;
}
return p[0][x];
}
set<int> s[maxn], d[maxn];
vi a;
int m;
void dodaj(int pos){
s[a[pos]].insert(pos);
if (pos < m){
int k = lca(a[pos], a[pos+1]);
d[k].insert(pos);
}
if (pos>1){
int k = lca(a[pos], a[pos-1]);
d[k].insert(pos-1);
}
}
void brisi(int pos){
s[a[pos]].erase(pos);
if (pos < m){
int k = lca(a[pos], a[pos+1]);
d[k].erase(pos);
}
if (pos > 1){
int k = lca(a[pos-1], a[pos]);
d[k].erase(pos-1);
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cerr.tie(nullptr);
int n, q;
cin >> n >> m >> q;
for (int i = 0; i < n - 1; ++i){
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
root(1);
for (int i = 1; i <= n; ++i){
e[i].clear();
}
for (int i = 2; i <= n; ++i){
e[p[0][i]].push_back(i);
}
dfs(1);
a = vi(m+1);
for (int i = 1; i <= m; ++i)
cin >> a[i];
for (int i = 1; i <= m; ++i){
dodaj(i);
}
for (int h = 0; h < q; ++h){
int z;
cin >> z;
if (z == 1){
int pos, val;
cin >> pos >> val;
brisi(pos);
a[pos] = val;
dodaj(pos);
continue;
}
int l, r, x;
cin >> l >> r >> x;
auto it = s[x].lower_bound(l);
if (it != s[x].end()){
int ind = *it;
if (ind <= r){
cout << ind << ' ' << ind << '\n';
continue;
}
}
it = d[x].lower_bound(l);
if (it != d[x].end()){
int ind = *it;
if (ind < r){
cout << ind << ' ' << ind+1 << '\n';
continue;
}
}
cout << "-1 -1\n";
}
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/
