[BJOI2015]骑士的旅行

内存限制：512 MB 时间限制：2000 ms

在一片古老的土地上，有一个繁荣的文明。

这片大地几乎被森林覆盖，有 $N$ 座城坐落其中。巧合的是，这 $N$ 座城由恰好 $N-1$ 条双向道路连接起来，使得任意两座城都是连通的。也就是说，这些城形成了树的结构，任意两座城之间有且仅有一条简单路径。

在这个文明中，骑士是尤其受到尊崇的职业。任何一名骑士，都是其家族乃至家乡的荣耀。Henry 从小就渴望成为一名能守护家乡、驱逐敌人的骑士。勤奋训练许多年后，Henry 终于满18岁了。他决定离开家乡，向那些成名已久的骑士们发起挑战！

根据 Henry 的调查，大陆上一共有 $M$ 名受封骑士，不妨编号为 $1$ 到 $M$。

第 $i$ 个骑士居住在城 $P_i$，武力值为 $F_i$。

Henry 计划进行若干次旅行，每次从某座城出发沿着唯一的简单路径前往另一座城，同时会挑战路线上武力值最高的 $K$ 个骑士（Henry 的体力有限，为了提高水平，当然要挑战最强的骑士）。如果路线上的骑士不足 $K$ 人，Henry 会挑战遇到的所有人。

每次旅行前，可能会有某些骑士的武力值或定居地发生变化，Henry 自然会打听消息，并对计划做出调整。

为了在每次旅行时做好充分准备，Henry 希望你能帮忙在每次旅行前计算出这条路线上他将挑战哪些对手。

第一行，一个整数 $N$，表示有 $N$ 座城，编号为 $1$ ~ $N$。

接下来 $N-1$ 行，每行两个整数 $U_i$ 和 $V_i$，表示城 $U_i$ 和城 $V_i$ 之间有一条道路相连。

第 $N+1$ 行，一个整数 $M$，表示有 $M$ 个骑士。

接下来 $M$ 行，每行两个整数 $F_i$ 和 $P_i$。按顺序依次表示编号为 $1$ ~ $M$ 的每名骑士的武力值和居住地。

第 $N+M+2$ 行，两个整数 $Q,K$，分别表示操作次数和每次旅行挑战的骑士数目上限。

接下来 $Q$ 行，每行三个整数 $T_i,X_i,Y_i$。$T_i$ 取值范围为 $\{1,2,3\}$，表示操作类型。

一共有以下三种类型的操作：

$T_i=1$ 时表示一次旅行，Henry 将从城 $X_i$ 出发前往城市 $Y_i$；

$T_i=2$ 时表示编号为 $X_i$ 的骑士的居住地搬到城 $Y_i$；

$T_i=3$ 时表示编号为 $X_i$ 的骑士的武力值修正为 $Y_i$。

输出若干行，依次为每个旅行的答案。

对每个 $T_i=1$ 的询问，输出一行，按从大到小的顺序输出 Henry 在这次旅行中挑战的所有骑士的武力值。如果路线上没有骑士，输出一行，为一个整数 $-1$。

100% 的数据中，$1 ≤ N, M ≤ 40,000$，$1 ≤ U_i, V_i, P_i ≤ N$，$1 ≤ Q ≤ 80,000$，$1 ≤ K ≤20$，旅行次数不超过 $40,000$ 次，武力值为不超过 $1,000$ 的正整数。

C0634 [BJOI2015]骑士的旅行