#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i,s) for(ll i=0; i<s ; i++)
#define f(i,a,b) for(ll i(a); i<b ; i++)
const ll INF = 1000000000000000000;
const ll N = 100001;
const ll MOD = 1000000007;
const ll modi = 1000000007;
const ll MAXN = 10000000000;
const ll rootval = 319;
using namespace std;
ll n,l;
vector<ll> adj[N];
ll timer;
vector<ll> tin, tout;
vector<vector<ll>> up;
void dfs(ll v, ll p)
{
tin[v] = ++timer;
up[v][0] = p;
for (ll i = 1; i <= l; ++i)
up[v][i] = up[up[v][i-1]][i-1];
for (ll u : adj[v]) {
if (u != p)
dfs(u, v);
}
tout[v] = ++timer;
}
bool is_ancestor(ll u, ll v)
{
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
ll lca(ll u, ll v)
{
if (is_ancestor(u, v))
return u;
if (is_ancestor(v, u))
return v;
for (ll i = l; i >= 0; --i) {
if (!is_ancestor(up[u][i], v))
u = up[u][i];
}
return up[u][0];
}
void preprocess(ll root) {
tin.resize(n);
tout.resize(n);
timer = 0;
l = ceil(log2(n));
up.assign(n, vector<ll>(l + 1));
dfs(root, root);
}
int main(){
ll m,q;
cin >> n >> m >> q;
rep(i,n-1){
ll u,v;
cin >> u >> v;
--u,--v;
adj[u].push_back(v);
adj[v].push_back(u);
}
ll arr[m];
ll lcarr[m];
rep(i,m){
cin >> arr[i];
--arr[i];
}
if(m == 1){
rep(i,q){
ll x;
cin >> x;
if(x == 1){
ll pos,v;
cin >> pos >> v;
--pos,--v;
arr[pos] = v;
}
else{
ll l,r,v;
cin >> l >> r >> v;
--l,--r,--v;
if(arr[l] == v){
cout << l+1 << " " << l+1 << endl;
}
else{
cout << -1 << " " << -1 << endl;
}
}
}
}
else{
preprocess(0);
set<ll> pos2[n];
set<ll> pos1[n];
rep(i,m){
pos1[arr[i]].insert(i);
}
rep(i,m-1){
ll lc = lca(arr[i],arr[i+1]);
pos2[lc].insert(i);
lcarr[i] = lc;
}
rep(i,q){
ll x;
cin >> x;
if(x == 1){
ll pos,v;
cin >> pos >> v;
--pos,--v;
ll val = arr[pos];
arr[pos] = v;
pos1[val].erase(pos);
pos1[v].insert(pos);
if(pos == 0){
pos2[lcarr[pos]].erase(pos);
ll lc = lca(arr[pos],arr[pos+1]);
lcarr[pos] = lc;
pos2[lcarr[pos]].insert(pos);
}
else if(pos == m-1){
pos2[lcarr[pos-1]].erase(pos-1);
ll lc = lca(arr[pos],arr[pos-1]);
lcarr[pos-1] = lc;
pos2[lcarr[pos-1]].insert(pos-1);
}
else{
pos2[lcarr[pos]].erase(pos);
ll lc = lca(arr[pos],arr[pos+1]);
lcarr[pos] = lc;
pos2[lcarr[pos]].insert(pos);
pos2[lcarr[pos-1]].erase(pos-1);
lc = lca(arr[pos],arr[pos-1]);
lcarr[pos-1] = lc;
pos2[lcarr[pos-1]].insert(pos-1);
}
}
else{
ll l,r,v;
cin >> l >> r >> v;
--l,--r,--v;
ll y = 1e18;
ll y1 = 1e18;
if(!pos1[v].empty()){
auto it = pos1[v].lower_bound(l);
y=*it;
}
if(!pos2[v].empty()){
auto it1 = pos2[v].lower_bound(l);
y1 = *it1;
}
if(y <= r){
cout << y+1 << " " << y+1 << endl;
}
else if(y1 <= r-1){
cout << y1+1 << " " << y1+2 << endl;
}
else{
cout << -1 << " " << -1 << endl;
}
}
}
}
}
