Knight Challenge on the Continent

Henry's investigation shows that there are \(M\) knights in the continent, numbered from 1 to \(M\). The \(i\)th knight resides in city \(P_i\) and has strength \(F_i\). The cities are connected in a tree with \(N\) nodes and \(N-1\) edges ensuring a unique simple path between any two cities.

Henry plans several trips. In each trip he travels from one city to another along the unique simple path. On his journey he will challenge the top \(K\) knights encountered on that path (if there are fewer than \(K\) knights, he challenges all of them). Prior to each trip, some knights may update their residing city or strength. For each trip, determine which knights Henry will challenge.

Note on Selection: When selecting knights, they are sorted primarily in descending order of their current strength. In case of ties, the knight with the smaller index is preferred.

inputFormat

The input begins with a line containing three integers: \(N\) (the number of cities), \(M\) (the number of knights), and \(Q\) (the number of operations).

Then follow \(N-1\) lines, each containing two integers \(u\) and \(v\) representing an edge between cities \(u\) and \(v\) in the tree.

The next line contains \(M\) integers: \(P_1, P_2, \dots, P_M\), indicating the initial city of each knight.

The following line contains \(M\) integers: \(F_1, F_2, \dots, F_M\), representing the strength of each knight.

Then follow \(Q\) lines, each describing an operation. An operation is either a query or an update:

• Type 1 (Query): The line starts with a 1 followed by three integers \(u\), \(v\), and \(k\), meaning Henry plans a trip from city \(u\) to city \(v\) and will challenge the top \(k\) knights on the path.
• Type 2 (Update): The line starts with a 2 followed by three integers \(i\), \(c\), and \(f\), meaning update knight \(i\) so that his new city is \(c\) and his new strength is \(f\).

outputFormat

For each query (operation type 1), output a line. The line begins with an integer representing the number of knights Henry will challenge, followed by the indices of the selected knights in order – sorted by descending strength (and by increasing index in case of ties). All numbers should be separated by a space.

sample

5 5 6
1 2
2 3
2 4
4 5
1 2 3 4 5
10 20 15 30 25
1 1 5 3
2 3 5 50
1 3 5 2
2 2 3 5
1 3 2 5
1 1 3 2

3 4 5 2
2 3 4
1 2
2 1 2