#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = int;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
using str = string;
using big_int = __int128_t;
const ld eps = 1e-7;
const ld PI = acos(-1);
#define all(c) (c).begin(), (c).end()
#define rall(c) ((c).rbegin()), ((c).rend())
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define fast ios_base::sync_with_stdio(0); cin.tie(0)
#define forn(i, n) for (ll i = 0; i < n; ++i)
#define sz(a) (ll)a.size()
#define endl '\n'
#define u_map unordered_map
#define mset multiset
//#define x first
//#define y second
#ifdef ONLINE_JUDGE
#define debug(x);
#else
#define debug(x) cerr << #x << ": " << x << endl;
#endif
str IO[2] = {"NO\n", "YES\n"};
str io[2] = {"no\n", "yes\n"};
str Io[2] = {"No\n", "Yes\n"};
//
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnd(1232423);
template<class T> bool inmin(T& x_, T y_) {return y_ < x_ ? (x_ = y_, true) : false;}
template<class T> bool inmax(T& x_, T y_) {return y_ > x_ ? (x_ = y_, true) : false;}
//const ll Mod = 1e9 + 7;
const ll Mod = 998244353;
//const ll Mod = 1e9 + 9;
//const ll Mod = 1234567891;
//const ll INF = 1e18;
template<class T> void add(T& x_, T y_) { x_ = (x_ + y_) % Mod; };
template<class T> void sub(T& x_, T y_) { x_ = (x_ + Mod - y_) % Mod; };
template<class T> void mul(T& x_, T y_) { x_ = (x_ * y_) % Mod; };
const ll Maxn = 2e5 + 10;
const ll Lg = 20;
vll gr[Maxn];
ll app[Maxn];
ll st[Lg][Maxn];
ll ans[Lg][Maxn];
ll d[Maxn];
ll dp[Maxn];
vll pth;
void init() {
dp[0] = -1;
for (ll i = 1; i < Maxn; ++i) {
dp[i] = dp[i / 2] + 1;
}
return;
}
void dfs(ll v, ll p) {
app[v] = sz(pth);
d[v] = d[p] + 1;
pth.pb(v);
for (ll adj : gr[v]) {
if (adj != p) {
dfs(adj, v);
pth.pb(v);
}
}
return;
}
ll lca(ll a, ll b) {
ll l = min(app[a], app[b]);
ll r = max(app[a], app[b]);
ll lg = dp[r - l + 1];
ll len = (1 << lg);
ll dep = st[lg][l];
ll res = ans[lg][l];
if (st[lg][r - len + 1] < dep) {
return ans[lg][r - len + 1];
}
return res;
}
const ll C = 1;
struct block {
u_map<ll, set<ll>> keys;
ll size;
void erase(ll x, ll key) {
keys[key].erase(x);
}
void insert(ll x, ll key) {
keys[key].insert(x);
}
ll get(ll key) {
return (keys[key].empty() ? -1 : *keys[key].begin());
}
};
inline void solve() {
ll n, m, q;
cin >> n >> m >> q;
forn (i, n - 1) {
ll u, v;
cin >> u >> v;
--u, --v;
gr[u].pb(v), gr[v].pb(u);
}
dfs(0, 0);
dfs(0, 0);
forn (i, sz(pth)) {
st[0][i] = d[pth[i]];
ans[0][i] = pth[i];
}
for (ll i = 1; i < Lg; ++i) {
ll len = (1 << i);
for (ll j = 0; j + len <= sz(pth); ++j) {
st[i][j] = st[i - 1][j];
ans[i][j] = ans[i - 1][j];
if (st[i][j] > st[i - 1][j + len / 2]) {
st[i][j] = st[i - 1][j + len / 2];
ans[i][j] = ans[i - 1][j + len / 2];
}
}
}
vll que(m);
forn (i, m) {
cin >> que[i];
--que[i];
}
vll lcas(m - 1);
forn (i, m - 1) {
lcas[i] = lca(que[i], que[i + 1]);
}
vector<block> dcL;
forn (i, sz(lcas)) {
ll id = i / C;
if (id == sz(dcL)) dcL.pb({});
dcL[id].size++;
dcL[id].insert(i, lcas[i]);
}
vector<block> dcV;
forn (i, sz(que)) {
ll id = i / C;
if (id == sz(dcV)) dcV.pb({});
dcV[id].size++;
dcV[id].insert(i, que[i]);
}
auto query = [&](ll l, ll r, ll key, vector<block> &dc, vector<ll> &arr) {
ll id = -1;
while (l <= r) {
if (l % C == 0 && l + dc[l / C].size - 1 <= r) {
ll nid = dc[l / C].get(key);
if (nid != -1) id = nid;
l += dc[l / C].size;
} else {
if (arr[l] == key) id = l;
++l;
}
}
return id;
};
while (q--) {
ll tp;
cin >> tp;
if (tp == 1) {
ll pos, v;
cin >> pos >> v;
--pos, --v;
dcV[pos / C].erase(pos, que[pos]);
if (pos - 1 >= 0) {
dcL[(pos - 1) / C].erase(pos - 1, lcas[pos - 1]);
}
if (pos + 1 < m) {
dcL[pos / C].erase(pos, lcas[pos]);
}
que[pos] = v;
dcV[pos / C].insert(pos, que[pos]);
if (pos - 1 >= 0) {
lcas[pos - 1] = lca(que[pos - 1], que[pos]);
dcL[(pos - 1) / C].insert(pos - 1, lcas[pos - 1]);
}
if (pos + 1 < m) {
lcas[pos] = lca(que[pos], que[pos + 1]);
dcL[pos / C].insert(pos, lcas[pos]);
}
continue;
}
ll l, r, v;
cin >> l >> r >> v;
--l, --r, --v;
ll id = query(l, r, v, dcV, que);
if (id != -1) {
cout << id + 1 << ' ' << id + 1 << endl;
continue;
}
if (l == r) {
cout << -1 << ' ' << -1 << endl;
continue;
}
--r;
id = query(l, r, v, dcL, lcas);
if (id == -1) {
cout << -1 << ' ' << -1 << endl;
continue;
}
ll ql = id + 1;
ll qr = ql + 1;
cout << ql << ' ' << qr << endl;
}
return;
}
int main() {
init();
fast;
//cout << fixed << satprecision(10);
ll test;
test = 1;
//cin >> test;
for (ll id = 0; id < test; ++id) solve();
return 0;
}
