#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vei;
typedef vector<vei> vevei;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int) a.size()
#define con cout << "NO\n"
#define coe cout << "YES\n";
#define str string
#define pb push_back
#define ff first
#define sc second
#define ss second
#define pii pair<int, int>
#define mxe max_element
#define mne min_element
#define stf shrink_to_fit
#define f(i, l, r) for (int i = (l); i < (r); i++)
#define double ld
struct LCA {
int n;
vector<vector<int>> g, up;
vector<int> tin, tout;
int timer = 0, l;
LCA() = default;
LCA(int n_, vector<vector<int>>& g_) {
n = n_;
g = g_;
l = (int)log2(n) + 1;
up.assign(n, vector<int>(l, 0));
tin.assign(n, 0);
tout.assign(n, 0);
dfs(0, 0);
}
void dfs(int v, int p) {
tin[v] = timer++;
up[v][0] = p;
f(i, 1, l) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
for (auto& u : g[v]) {
if (u != p) {
dfs(u, v);
}
}
tout[v] = timer++;
}
bool parent(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (parent(a, b)) return a;
if (parent(b, a)) return b;
for (int i = l - 1; i >= 0; i--) {
if (!parent(up[a][i], b)) {
a = up[a][i];
}
}
return up[a][0];
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, q; cin >> n >> m >> q;
vector<vector<int>> g(n);
f(i, 0, n - 1) {
int u, v; cin >> u >> v;
u--; v--;
g[u].pb(v);
g[v].pb(u);
}
LCA lc(n, g);
vector<int> a(m);
f(i, 0, m) { cin >> a[i]; a[i]--; }
vector<int> lcas(m - 1);
vector<set<int>> pos(n), pos2(n);
f(i, 0, m - 1) {
lcas[i] = lc.lca(a[i], a[i + 1]);
pos[lcas[i]].insert(i);
pos2[a[i]].insert(i);
}
pos2[a[m - 1]].insert(m - 1);
while (q--) {
int t; cin >> t;
if (t == 1) {
int p, v; cin >> p >> v;
p--;
v--;
pos2[a[p]].erase(p);
pos2[v].insert(p);
if (p > 0) {
pos[lcas[p - 1]].erase(p - 1);
lcas[p - 1] = lc.lca(a[p - 1], v);
pos[lcas[p - 1]].insert(p - 1);
}
if (p < m - 1) {
pos[lcas[p]].erase(p);
lcas[p] = lc.lca(v, a[p + 1]);
pos[lcas[p]].insert(p);
}
a[p] = v;
}
else {
int l, r, x; cin >> l >> r >> x;
l--; r--; x--;
auto it = pos2[x].lower_bound(l);
if (it != pos2[x].end() && *it <= r) {
cout << *it + 1 << ' ' << *it + 1 << '\n';
continue;
}
auto it2 = pos[x].lower_bound(l);
if (r - l + 1 >= 2 && it2 != pos[x].end() && *it2 <= r - 1) {
cout << *it2 + 1 << ' ' << *it2 + 2 << '\n';
continue;
}
cout << "-1 -1\n";
}
}
return 0;
}
