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