#include <bits/stdc++.h>
#define file ""
#define all(x) x.begin(), x.end()
#define sc second
#define fr first
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;
const int N = 3e5 + 5;
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};
int up[N][20], timer;
int tin[N], tout[N];
int n, m, q, c[N];
vector<int> g[N];
set<int> s[N], all[N];
void dfs(int x, int pr) {
up[x][0] = pr;
tin[x] = timer++;
for (int i = 1; i <= 18; i++)
up[x][i] = up[up[x][i - 1]][i - 1];
for (int to : g[x])
if (to != pr)
dfs(to, x);
tout[x] = timer++;
}
bool upper(int x, int y) {
return tin[x] <= tin[y] && tout[x] >= tout[y];
}
int lca(int x, int y) {
if (upper(x, y)) return x;
if (upper(y, x)) return y;
for (int i = 18; i >= 0; i--)
if (!upper(up[x][i], y) && up[x][i])
x = up[x][i];
return up[x][0];
}
void update() {
int pos, val;
cin >> pos >> val;
int p = c[pos];
all[p].erase(pos);
all[val].insert(pos);
c[pos] = val;
if (pos == n) {
int v = lca(c[n - 1], p);
s[v].erase(n - 1);
v = lca(c[n - 1], c[n]);
s[v].insert(n - 1);
}
else if (pos == 1) {
int v = lca(p, c[2]);
s[v].erase(1);
v = lca(c[1], c[2]);
s[v].insert(1);
} else {
int v = lca(p, c[pos - 1]);
s[v].erase(pos - 1);
v = lca(c[pos], c[pos - 1]);
s[v].insert(pos - 1);
v = lca(c[pos + 1], p);
s[v].erase(pos);
v = lca(c[pos + 1], c[pos]);
s[v].insert(pos);
}
}
void get() {
int l, r, v;
cin >> l >> r >> v;
auto pos = *s[v].upper_bound(l - 1);
if (pos < r) {
cout << pos << " " << pos + 1 << endl;
return;
}
pos = *all[v].upper_bound(l - 1);
if (pos <= r) {
cout << pos << " " << pos << endl;
return;
}
cout << -1 << " " << -1 << "\n";
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
srand(time(nullptr));
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
s[i].insert(n + 1), all[i].insert(n + 1);
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
dfs(1, 0);
for (int i = 1; i <= m; i++) cin >> c[i];
for (int i = 1; i <= m; i++)
all[c[i]].insert(i);
for (int i = 1; i < m; i++)
s[lca(c[i], c[i + 1])].insert(i);
while (q--) {
int t;
cin >> t;
if (t == 1) update();
if (t == 2) get();
}
return 0;
}
