#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()
using ll = long long;
const int mod = 1e9+7;
vector<vector<int>> adj;
vector<int> depth;
vector<array<int, 20>> up;
void dfs(int u, int p = -1) {
for (int v : adj[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
up[v][0] = u;
for (int l = 1; l < 20; ++l) {
up[v][l] = up[up[v][l-1]][l-1];
}
dfs(v, u);
}
}
}
void solve(int tc) {
int n, m, q;
cin >> n >> m >> q;
adj.resize(n); up.resize(n); depth.resize(n);
for (int i = 0; i < n-1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0);
auto get_lca = [&] (int u, int v) {
if (depth[u] < depth[v])
swap(u, v);
int k = depth[u] - depth[v];
for (int l = 19; l >= 0; --l)
if (k & (1<<l))
u = up[u][l];
if (u == v)
return u;
for (int l = 19; l >= 0; --l) {
if (up[u][l] != up[v][l]) {
u = up[u][l];
v = up[v][l];
}
}
return up[u][0];
};
vector<set<int>> lca(n);
vector<set<int>> pos(n);
vector<int> a(m);
for (auto &x : a) {
cin >> x;
--x;
}
for (int i = 0; i < m; ++i)
pos[a[i]].insert(i);
for (int i = 0; i < m-1; ++i) {
int u = get_lca(a[i], a[i+1]);
lca[u].insert(i);
}
while (q--) {
int x;
cin >> x;
if (x == 1) {
int p, v;
cin >> p >> v;
--p, --v;
pos[a[p]].erase(p);
pos[v].insert(p);
if (p) {
lca[get_lca(a[p-1], a[p])].erase(p-1);
lca[get_lca(a[p-1], v)].insert(p-1);
}
if (p < m-1) {
lca[get_lca(a[p], a[p+1])].erase(p);
lca[get_lca(v, a[p+1])].insert(p);
}
a[p] = v;
} else {
int l, r, v;
cin >> l >> r >> v;
--l, --r, --v;
auto it = pos[v].lower_bound(l);
int p = *it;
if (it != pos[v].end() and p <= r) {
cout << p+1 << " " << p+1 << '\n';
continue;
}
it = lca[v].lower_bound(l);
p = *it;
if (it != lca[v].end() and p < r) {
cout << p+1 << " " << p+2 << '\n';
continue;
}
cout << "-1 -1\n";
}
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int tc = 1;
//cin >> tc;
for (int i = 1; i <= tc; ++i) solve(i);
return 0;
}
