#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
const int maxlog = 19;
int n, m, q;
vector<int> tree[maxn];
int jump[maxn][maxlog + 1];
int depth[maxn];
void dfsLCA(int node, int par, int dep)
{
depth[node] = dep;
for (int i = 0; i < tree[node].size(); ++i)
{
if (tree[node][i] != par)
{
dfsLCA(tree[node][i], node, dep + 1);
jump[tree[node][i]][0] = node;
}
}
}
void buildSparse()
{
jump[1][0] = 1;
for (int log = 1; log <= maxlog; ++log)
{
for (int node = 1; node <= n; ++node)
{
jump[node][log] = jump[jump[node][log - 1]][log - 1];
}
}
}
int findLCA(int x, int y)
{
if (depth[x] < depth[y])
{
swap(x, y);
}
int diff = depth[x] - depth[y];
for (int i = 0; i <= maxlog; ++i)
{
if ((diff & (1 << i)) != 0)
{
x = jump[x][i];
diff -= (1 << i);
if (diff == 0)
{
break;
}
}
}
if (x == y)
{
return x;
}
for (int log = maxlog; log >= 0; --log)
{
if (jump[x][log] != jump[y][log])
{
x = jump[x][log];
y = jump[y][log];
}
}
return jump[x][0];
}
int sequence[maxn];
set<int> byValue[maxn];
set<int> byLCA[maxn];
void updateQuery(int pos, int newNode)
{
int curr = sequence[pos];
byValue[curr].erase(pos);
if (pos >= 2)
{
int prv = sequence[pos - 1];
//cout << "delete LCA " << findLCA(prv, curr) << " on pos " << pos << endl;
//cout << "add LCA " << findLCA(prv, newNode) << " on pos " << pos << endl;
byLCA[findLCA(prv, curr)].erase(pos);
byLCA[findLCA(prv, newNode)].insert(pos);
}
if (pos <= m - 1)
{
int nxt = sequence[pos + 1];
//cout << "delete LCA " << findLCA(curr, nxt) << " on pos " << pos + 1 << endl;
//cout << "add LCA " << findLCA(newNode, nxt) << " on pos " << pos + 1 << endl;
byLCA[findLCA(curr, nxt)].erase(pos + 1);
byLCA[findLCA(newNode, nxt)].insert(pos + 1);
}
sequence[pos] = newNode;
byValue[sequence[pos]].insert(pos);
}
void solveQuery(int from, int to, int nodeLCA)
{
if (!byValue[nodeLCA].empty())
{
auto it = byValue[nodeLCA].lower_bound(from);
if (it != byValue[nodeLCA].end() && (*it) <= to)
{
int idx = (*it);
cout << idx << ' ' << idx << "\n";
return;
}
}
if (!byLCA[nodeLCA].empty())
{
auto it = byLCA[nodeLCA].lower_bound(from + 1);
if (it != byLCA[nodeLCA].end() && (*it) <= to)
{
int idx = (*it);
cout << idx - 1 << ' ' << idx << "\n";
return;
}
}
cout << -1 << ' ' << -1 << "\n";
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n >> m >> q;
for (int i = 1; i <= n - 1; ++i)
{
int x, y;
cin >> x >> y;
tree[x].push_back(y);
tree[y].push_back(x);
}
dfsLCA(1, -1, 0);
buildSparse();
for (int i = 1; i <= m; ++i)
{
cin >> sequence[i];
byValue[sequence[i]].insert(i);
}
for (int i = 2; i <= m; ++i)
{
//cout << "add " << findLCA(sequence[i - 1], sequence[i]) << " on position " << i << endl;
byLCA[findLCA(sequence[i - 1], sequence[i])].insert(i);
}
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int pos, val;
cin >> pos >> val;
updateQuery(pos, val);
}
else
{
int l, r, node;
cin >> l >> r >> node;
solveQuery(l, r, node);
}
}
return 0;
}
