#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <bitset>
#include <vector>
#include <stack>
#include <set>
typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXLOG = 18;
int n, m, q;
struct Sparse
{
int sparse[MAXLOG][MAXN];
int depth[MAXN];
int par[MAXN];
void build(int _depth[], int _par[])
{
for (int i = 1 ; i <= n ; ++i)
{
par[i] = _par[i];
depth[i] = _depth[i];
sparse[0][i] = par[i];
}
for (int log = 1 ; (1 << log) <= n ; ++log)
{
for (int i = 1 ; i <= n ; ++i)
{
sparse[log][i] = sparse[log - 1][sparse[log - 1][i]];
}
}
}
int equalize(int x, int y)
{
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (depth[sparse[log][x]] >= depth[y])
{
x = sparse[log][x];
}
}
return x;
}
int calcLCA(int x, int y)
{
if (x == y)
{
return x;
}
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (sparse[log][x] != sparse[log][y])
{
x = sparse[log][x];
y = sparse[log][y];
}
}
return sparse[0][x];
}
int findLCA(int x, int y)
{
if (depth[x] < depth[y])
{
std::swap(x, y);
}
return calcLCA(equalize(x, y), y);
}
};
int a[MAXN];
Sparse sparse;
int par[MAXN];
int depth[MAXN];
std::set <int> byLCA[MAXN];
std::set <int> byLCA2[MAXN];
std::vector <int> g[MAXN];
void dfs(int node, int p)
{
par[node] = p;
depth[node] = depth[p] + 1;
for (const int &u : g[node])
{
if (u == p)
{
continue;
}
dfs(u, node);
}
}
void solve()
{
dfs(1, 0);
sparse.build(depth, par);
for (int i = 1 ; i <= m ; ++i)
{
byLCA[a[i]].insert(i);
if (i != m)
{
byLCA2[sparse.findLCA(a[i], a[i + 1])].insert(i);
}
}
for (int query = 1 ; query <= q ; ++query)
{
int qType;
std::cin >> qType;
if (qType == 1)
{
int pos, node;
std::cin >> pos >> node;
byLCA[a[pos]].erase(byLCA[a[pos]].find(pos));
if (pos < m)
{
int lca = sparse.findLCA(a[pos], a[pos + 1]);
byLCA2[lca].erase(byLCA2[lca].find(pos));
}
if (pos > 1)
{
int lca = sparse.findLCA(a[pos], a[pos - 1]);
byLCA2[lca].erase(byLCA2[lca].find(pos - 1));
}
a[pos] = node;
byLCA[a[pos]].insert(pos);
if (pos < m)
{
int lca = sparse.findLCA(a[pos], a[pos + 1]);
byLCA2[lca].insert(pos);
}
if (pos > 1)
{
int lca = sparse.findLCA(a[pos], a[pos - 1]);
byLCA2[lca].insert(pos - 1);
}
continue;
}
int l, r, node;
std::cin >> l >> r >> node;
auto it = byLCA[node].lower_bound(l);
if (it != byLCA[node].end() && (*it) <= r)
{
std::cout << (*it) << ' ' << (*it) << '\n';
continue;
}
it = byLCA2[node].lower_bound(l);
if (it != byLCA2[node].end() && (*it) < r)
{
std::cout << (*it) << ' ' << (*it) + 1 << '\n';
continue;
}
std::cout << -1 << ' ' << -1 << '\n';
}
}
void input()
{
std::cin >> n >> m >> q;
for (int i = 2 ; i <= n ; ++i)
{
int u, v;
std::cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1 ; i <= m ; ++i)
{
std::cin >> a[i];
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
