[BJOI2015] 骑士的旅行

题目背景

在一片古老的土地上,有一个繁荣的文明。 这片大地几乎被森林覆盖,有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$。

输入输出样例

输入样例 #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

输出样例 #1

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的正整数。