#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() template <class T> struct RMQ { // 0-based vector<vector<T>> rmq; T kInf = numeric_limits<T>::max(); void build(const vector<T>& V) { int n = V.size(), on = 1, dep = 1; while (on < n) on *= 2, ++dep; rmq.assign(dep, V); for (int i = 0; i < dep - 1; ++i) for (int j = 0; j < n; ++j) { rmq[i + 1][j] = min(rmq[i][j], rmq[i][min(n - 1, j + (1 << i))]); } } T query(int a, int b) { // [a, b) if (b <= a) return kInf; int dep = 31 - __builtin_clz(b - a); // log(b - a) return min(rmq[dep][a], rmq[dep][b - (1 << dep)]); } }; struct LCA { // 0-based vector<int> enter, depth, exxit; vector<vector<int>> G; vector<pair<int, int>> linear; RMQ<pair<int, int>> rmq; int timer = 0; LCA() {} LCA(int n) : enter(n, -1), exxit(n, -1), depth(n), G(n), linear(2 * n) {} void dfs(int node, int dep) { linear[timer] = {dep, node}; enter[node] = timer++; depth[node] = dep; for (auto vec : G[node]) if (enter[vec] == -1) { dfs(vec, dep + 1); linear[timer++] = {dep, node}; } exxit[node] = timer; } void add_edge(int a, int b) { G[a].push_back(b); G[b].push_back(a); } void build(int root) { dfs(root, 0); rmq.build(linear); } int query(int a, int b) { a = enter[a], b = enter[b]; return rmq.query(min(a, b), max(a, b) + 1).second; } int dist(int a, int b) { return depth[a] + depth[b] - 2 * depth[query(a, b)]; } }; const int N = 2e6 + 1; set<int> one[N], two[N]; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; LCA lca(n); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; lca.add_edge(--u, --v); } lca.build(0); vector<int> a(m); for (int i = 0; i < m; i++) { cin >> a[i]; a[i]--; one[a[i]].insert(i); if (i > 0) { two[lca.query(a[i - 1], a[i])].insert(i - 1); } } while (q--) { int t; cin >> t; if (t == 1) { int i, v; cin >> i >> v; i--, v--; one[a[i]].erase(i); if (i > 0) { two[lca.query(a[i - 1], a[i])].erase(i - 1); } if (i + 1 < n) { two[lca.query(a[i], a[i + 1])].erase(i); } a[i] = v; one[a[i]].insert(i); if (i > 0) { two[lca.query(a[i - 1], a[i])].insert(i - 1); } if (i + 1 < n) { two[lca.query(a[i], a[i + 1])].insert(i); } } else { int l, r; int v; cin >> l >> r >> v; v--, l--, r--; int pl = -2, pr = -2; { auto it = one[v].lower_bound(l); if (it != one[v].end() && *it <= r) pl = pr = *it; } { auto it = two[v].lower_bound(l); if (it != two[v].end() && *it < r) { pl = *it; pr = pl + 1; } } cout << pl + 1 << ' ' << pr + 1 << '\n'; } } return 0; }