J. Звездный Союз и Кибер-вирусы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В далеком будущем, в галактике под управлением Звездного Союза, межзвездные корабли и планеты образуют сложную сеть, являющуюся деревом. Эта сеть состоит из $$$n$$$ вершин. Союз сталкивается с серьезной угрозой — $$$m$$$ типов кибер-вирусов, которые могут быстро распространяться через сеть и заражать все планеты и корабли.

Каждый из $$$m$$$ типов кибер-вирусов обладает уникальными свойствами и может заражать соседние вершины в сети. В момент времени $$$t$$$, если планета или корабль $$$v$$$ заражены вирусом типа $$$i$$$, то в момент времени $$$t + 1$$$ все соседние вершины также будут заражены этим вирусом. Задача Звездного Союза — контролировать и отслеживать распространение вирусов, чтобы предотвратить катастрофические последствия.

Звездный Союз создал командный центр для управления распространением кибер-вирусов. К ним поступают запросы трех типов:

  1. Внедрение вируса:

    В момент времени $$$time$$$ вершина $$$v$$$ заражается кибер-вирусом типа $$$i$$$. Важно отметить, что каждый кибер-вирус типа $$$i$$$ уникален, и моменты времени $$$time$$$ не обязательно возрастают.

  2. Удаление вируса:

    Нужно удалить кибер-вирус типа $$$i$$$, что означает, что этот вирус больше не учитывается при анализе.

  3. Анализ заражений:

    Нужно определить минимальное время $$$t$$$, когда найдется вершина, которая заражена всеми не удаленными кибер-вирусами на отрезке $$$[l, r]$$$, то есть такая вершина $$$v$$$, что она заражена всеми вирусами на отрезке. Также необходимо вывести все вершины, которые будут заражены каждым кибер-вирусом из этого диапазона в момент $$$t$$$.

Изначально ни одна из вершин не заражена никаким вирусом.

Входные данные

Первая строка входных данных $$$n$$$, $$$m$$$ и $$$q$$$ $$$(2 \le n,m,q \le 2 \cdot 10^5)$$$ — размер графа, количество кибер-вирусов, и количество запросов.

Следующие $$$n - 1$$$ строк ввода содержат по два целых числа $$$u$$$ и $$$v$$$ $$$(1 \le u,v \le n)$$$, обозначающие ребра в графе.

Следующие $$$q$$$ строк содержат целое число $$$t(1 \le t \le 3)$$$ — тип запроса, а также

Если $$$t = 1$$$, то строка содержит дополнительно $$$3$$$ целых числа $$$time,v,i$$$ $$$(0 \le time \le n$$$, $$$1 \le v \le n$$$, $$$1 \le i \le m)$$$.

Если $$$t = 2$$$, строка будет содержать еще $$$1$$$ целое число $$$i$$$ $$$(1 \le i \le m)$$$.

Если $$$t = 3$$$, строка будет содержать еще $$$2$$$ целых числа $$$l,r$$$ $$$(1 \le l,r \le m)$$$. Гарантируется, что в данном диапазоне существует хотя бы 1 внедренный вирус, который еще не был удален.

Все $$$i$$$ в запросах Внедрения и Удаления вируса уникальны.

Выходные данные

Выведите ответ на каждый запрос Анализа заражений. Первая строка ответа должна содержать два целых числа, минимальное время $$$t$$$, когда найдется вершина, зараженный всеми не удаленными кибер-вирусами из диапазона, а также количество вершин, зараженных каждым кибер-вирусом из диапазона в момент времени $$$t$$$. Следующая строка должна содержать номера всех зараженных вершин в отсортированном, по номеру, порядке.

Гарантируется, что суммарное количество вершин во всех запросах не превосходит $$$10^7$$$.

Пример
Входные данные
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
Выходные данные
0 1
2 
2 2
1 3 
1 1
3