#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
const int LOGN = 19;
vector<int> adj[MAXN];
int tin[MAXN], tout[MAXN], timer;
int up[MAXN][LOGN];
int a[MAXN];
int n, m, q;
void dfs(int v, int p) {
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1; i < LOGN; i++)
up[v][i] = up[up[v][i - 1]][i - 1];
for (int u : adj[v]) {
if (u != p) dfs(u, v);
}
tout[v] = timer;
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int get_lca(int u, int v) {
if (u == 0) return v;
if (v == 0) return u;
if (is_ancestor(u, v)) return u;
if (is_ancestor(v, u)) return v;
for (int i = LOGN - 1; i >= 0; i--) {
if (!is_ancestor(up[u][i], v))
u = up[u][i];
}
return up[u][0];
}
struct Node {
int lca_val;
int min_t, max_t;
} tree[4 * MAXN];
Node merge(Node l, Node r) {
if (l.lca_val == 0) return r;
if (r.lca_val == 0) return l;
return {get_lca(l.lca_val, r.lca_val), min(l.min_t, r.min_t), max(l.max_t, r.max_t)};
}
void build(int node, int start, int end) {
if (start == end) {
tree[node] = {a[start], tin[a[start]], tin[a[start]]};
return;
}
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
void update(int node, int start, int end, int pos, int val) {
if (start == end) {
tree[node] = {val, tin[val], tin[val]};
return;
}
int mid = (start + end) / 2;
if (pos <= mid) update(2 * node, start, mid, pos, val);
else update(2 * node + 1, mid + 1, end, pos, val);
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
Node range_query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return {0, (int)2e9, -1};
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return merge(range_query(2 * node, start, mid, l, r), range_query(2 * node + 1, mid + 1, end, l, r));
}
int find_first_not(int node, int start, int end, int L, int R, int v) {
if (start > R || end < L || (tin[v] <= tree[node].min_t && tree[node].max_t <= tout[v]))
return -1;
if (start == end) return start;
int mid = (start + end) / 2;
int res = find_first_not(2 * node, start, mid, L, R, v);
if (res == -1) res = find_first_not(2 * node + 1, mid + 1, end, L, R, v);
return res;
}
void solve() {
int L, R, V;
cin >> L >> R >> V;
int cur = L;
while (cur <= R) {
int next_not = find_first_not(1, 1, m, cur, R, V);
int segment_end = (next_not == -1) ? R : next_not - 1;
if (segment_end >= cur) {
Node res = range_query(1, 1, m, cur, segment_end);
if (res.lca_val == V) {
cout << cur << " " << segment_end << "\n";
return;
}
}
if (next_not == -1) break;
cur = next_not + 1;
}
cout << "-1 -1\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m >> q;
for (int i = 0, u, v; i < n - 1; i++) {
cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
dfs(1, 1);
for (int i = 1; i <= m; i++) cin >> a[i];
build(1, 1, m);
while (q--) {
int t; cin >> t;
if (t == 1) {
int p, v; cin >> p >> v;
a[p] = v;
update(1, 1, m, p, v);
} else solve();
}
return 0;
}
