#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
template <class F> struct fixed : private F {
explicit fixed(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
constexpr int LOG = 20;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M, Q;
std::cin >> N >> M >> Q;
vector<vector<int>> graph(N);
for (int i = 0; i < N - 1; ++i) {
int a, b;
std::cin >> a >> b;
a -= 1;
b -= 1;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<int> in(N), out(N), depth(N), tour;
tour.reserve(2 * N - 2);
fixed([&](auto&& dfs, const int u, const int p) -> void {
in[u] = (int)tour.size();
tour.push_back(u);
for (const int v : graph[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u);
tour.push_back(u);
}
}
out[u] = (int)tour.size();
})(0, -1);
const auto select = [&](const int i, const int j) {
return depth[i] < depth[j] ? i : j;
};
array<vector<int>, LOG> table = {};
table[0] = tour;
for (int d = 0; d + 1 < LOG; ++d) {
const int n = std::max(0, (int)table[d].size() - (1 << d));
table[d + 1].resize(n);
for (int i = 0; i < n; ++i) {
table[d + 1][i] = select(table[d][i], table[d][i + (1 << d)]);
}
}
const auto lca = [&](const int u, const int v) {
const int l = std::min(in[u], in[v]);
const int r = std::max(out[u], out[v]);
const int t = 31 - __builtin_clz(r - l);
return select(table[t][l], table[t][r - (1 << t)]);
};
vector<std::set<int>> one(N), two(N);
vector<int> A(M), B(M - 1);
for (int i = 0; i < M; ++i) {
std::cin >> A[i];
A[i] -= 1;
one[A[i]].insert(i);
}
for (int i = 0; i < M - 1; ++i) {
B[i] = lca(A[i], A[i + 1]);
two[B[i]].insert(i);
}
const auto find = [&](const std::set<int>& set, const int l, const int r) {
const auto itr = set.lower_bound(l);
return (itr != set.end() and *itr < r) ? *itr : -1;
};
while (Q--) {
int t;
std::cin >> t;
if (t == 1) {
int p, v;
std::cin >> p >> v;
p -= 1;
v -= 1;
one[A[p]].erase(p);
A[p] = v;
one[A[p]].insert(p);
if (p > 0) {
two[B[p - 1]].erase(p - 1);
B[p - 1] = lca(A[p - 1], A[p]);
two[B[p - 1]].insert(p - 1);
}
if (p + 1 < M) {
two[B[p]].erase(p);
B[p] = lca(A[p], A[p + 1]);
two[B[p]].insert(p);
}
} else {
int l, r, v;
std::cin >> l >> r >> v;
l -= 1;
v -= 1;
if (const int t = find(one[v], l, r); t != -1) {
std::cout << t + 1 << ' ' << t + 1 << '\n';
} else if (const int t = find(two[v], l, r - 1); t != -1) {
std::cout << t + 1 << ' ' << t + 2 << '\n';
} else {
std::cout << -1 << ' ' << -1 << '\n';
}
}
}
return 0;
}
/*
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
*/
