J. Star Union and Cyber-viruses
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In the distant future, in a galaxy governed by the Star Union, interstellar ships and planets form a complex network, resembling a tree. This network consists of $$$n$$$ vertices. The Union faces a serious threat — $$$m$$$ types of cyber-viruses that can rapidly spread through the network and infect all planets and ships.

Each of the $$$m$$$ types of cyber-viruses has unique properties and can infect neighboring vertices in the network. At time $$$t$$$, if a planet or ship $$$v$$$ is infected with a virus of type $$$i$$$, then at time $$$t + 1$$$ all neighboring vertices will also be infected with this virus. The Star Union's task is to control and track the spread of viruses to prevent catastrophic consequences.

The Star Union has created a command center to manage the spread of cyber-viruses. They receive requests of three types:

  1. Virus Insertion:

    At time $$$time$$$, vertex $$$v$$$ is infected with a cyber-virus of type $$$i$$$. It is important to note that each cyber-virus of type $$$i$$$ is unique, and the times $$$time$$$ do not necessarily increase.

  2. Virus Removal:

    You need to remove the cyber-virus of type $$$i$$$, which means that this virus is no longer considered in the analysis.

  3. Infection Analysis:

    You need to determine the minimum time $$$t$$$ when there is a vertex that is infected with all non-removed cyber-viruses on the segment $$$[l, r]$$$, that is, a vertex $$$v$$$ such that it is infected with all viruses on the segment. You also need to output all vertices that will be infected with each cyber-virus from this range at time $$$t$$$.

Initially, none of the vertices are infected with any virus.

Input

The first line of the input data contains $$$n$$$, $$$m$$$, and $$$q$$$ $$$(2 \le n,m,q \le 2 \cdot 10^5)$$$ — the size of the graph, the number of cyber-viruses, and the number of requests.

The next $$$n - 1$$$ lines of input contain two integers $$$u$$$ and $$$v$$$ $$$(1 \le u,v \le n)$$$, denoting the edges in the graph.

The next $$$q$$$ lines contain an integer $$$t(1 \le t \le 3)$$$ — the type of request, as well as

If $$$t = 1$$$, then the line will contain an additional $$$3$$$ integers $$$time,v,i$$$ $$$(0 \le time \le n$$$, $$$1 \le v \le n$$$, $$$1 \le i \le m)$$$.

If $$$t = 2$$$, the line will contain another $$$1$$$ integer $$$i$$$ $$$(1 \le i \le m)$$$.

If $$$t = 3$$$, the line will contain another $$$2$$$ integers $$$l,r$$$ $$$(1 \le l,r \le m)$$$. It is guaranteed that there is at least 1 inserted virus in this range that has not yet been removed.

All $$$i$$$ in Virus Insertion and Virus Removal requests are unique.

Output

Output the answer to each Infection Analysis request. The first line of the answer should contain two integers, the minimum time $$$t$$$ when there is a vertex infected with all non-removed cyber-viruses from the range, as well as the number of vertices infected with each cyber-virus from the range at time $$$t$$$. The next line should contain the numbers of all infected vertices in sorted order by number.

It is guaranteed that the total number of vertices in all requests does not exceed $$$10^7$$$.

Example
Input
3 2 6
1 2
1 3
1 0 2 1
3 1 2
1 1 3 2
3 1 2
2 1
3 1 2
Output
0 1
2 
2 2
1 3 
1 1
3