Background

On an ancient land, there was a prosperous civilization.

This land was almost covered by forests, and there were $N$ cities scattered within it. By coincidence, these $N$ cities were connected by exactly $N-1$ bidirectional roads, so that any two cities were connected. In other words, these cities form a tree structure, and between any two cities there exists exactly one simple path.

In this civilization, being a knight was an especially respected profession. Any knight was the pride of their family and hometown. Henry had long dreamed of becoming a knight who could protect his hometown and drive away enemies. After training hard for many years, Henry finally turned 18. He decided to leave his hometown and challenge those famous knights.

Problem Description

According to Henry’s investigation, there are a total of $M$ titled knights on the continent, numbered from $1$ to $M$. The $i$-th knight lives in city $P_i$ and has combat power $F_i$.

Henry plans to make several journeys. In each journey, he starts from some city and travels along the unique simple path to another city, and he will challenge the strongest $K$ knights (Henry has limited stamina, and to improve himself, of course he challenges the strongest knights). If there are fewer than $K$ knights on the route, Henry will challenge everyone he meets.

Before each journey, some knights’ combat power or residence may change. Henry will naturally gather information and adjust his plan.

To be fully prepared for each journey, Henry wants you to help compute which opponents he will challenge on that route before each journey.

Input Format

The first line contains an integer $N$, meaning there are $N$ cities, numbered from $1$ to $N$.

The next $N-1$ lines each contain two integers $u_i$ and $v_i$, indicating that there is a road between city $u_i$ and city $v_i$.

Line $N+1$ contains an integer $M$, meaning there are $M$ knights.

The next $M$ lines each contain two integers $F_i$ and $P_i$, describing in order the combat power and residence of each knight numbered from $1$ to $M$.

Line $N+M+2$ contains two integers $Q$ and $K$, meaning the number of operations and the maximum number of knights challenged in each journey.

The next $Q$ lines each contain three integers $T_i$, $X_i$, and $Y_i$. $T_i \in \{1,~2,~3\}$ indicates the operation type.

There are three types of operations:

When $T_i=1$, it means a journey: Henry will travel from city $X_i$ to city $Y_i$.

When $T_i=2$, it means the residence of knight $X_i$ is moved to city $Y_i$.

When $T_i=3$, it means the combat power of knight $X_i$ is changed to $Y_i$.

Output Format

Output several lines, in order, as the answers for each journey.

For each query with $T_i=1$, output one line listing, in decreasing order, the combat power values of all knights Henry challenges in this journey. If there are no knights on the route, output one line containing the integer $-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

Hint

Constraints: for $100\%$ of the testdata, $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$. The number of journeys does not exceed 40,000. Combat power values are positive integers not exceeding 1,000.

Translated by ChatGPT 5