题目背景

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

这片大地几乎被森林覆盖，有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 \sim N$。

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

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

接下来M行，每行两个整数 $F_i$ 和 $P_i$ 。按顺序依次表示编号为 $1 \sim 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$。

5  
1 2  
1 3  
2 4  
2 5  
4  
10 1  
6 1  
14 5  
7 3  
5 3  
1 2 3  
1 5 3  
1 4 4  
2 1 4  
1 2 3

10 7 6  
14 10 7  
-1  
7 6

提示

100%的数据中，$1 \leq N,~M \leq 40,000,~1 \leq Ui,~Vi,~Pi \leq N,~1\leq Q \leq 80,000,~1 \leq K \leq 20$，旅行次数不超过 40,000 次，武力值为不超过1,000的正整数。