Бразилия

В фильме Терри Гиллиама "Бразилия" мы знакомимся с мрачным миром, которым управляет переросток из всеохватывающей бюрократической системы.

В то время как существуют некоторые его сходства с миром Оруэлла, изображенного в Девятнадцать Восемьдесят четыре, миру в Бразилии не хватает эффективности. Бюрократическая система полностью лишена функциональности, а весь мир полностью зависит от старых и плохо работающих машин.

В целом, Бразилия является фильмом, который стоит посмотреть. Изображенная во многих его сценах проблема навеяна бюрократической системой.

Вот основные положения системы:

• Существует неограниченное количество бюрократов. В нашей задаче будем нумеровать их числами от 1 до 10^9.

• Бюрократы обрабатывают формы. Каждой формой является лист бумаги. Каждая форма имеет ID код: целое число между 1 и 10^9 включительно. Может существовать несколько форм с одним ID.

• В каждый момент времени каждый бюрократ имеет ноль или более форм на своем столе. Все эти формы всегда расположены в виде одной стопки.

• Постоянно жители приходят к бюрократам заполнять новые формы. Новая форма заполняется и отправляется любому бюрократу. Это бюрократ принимает форму и помещает ее на вершине своей кучи.

• Время от времени бюрократ может решить, что кипа его необработанных форм слишком велика. В этом случае он ждет, когда другой бюрократ на минутку отвлечется. Как только это произойдет, наш бюрократ берет всю свою кучу форм и помещает ее на вершину кучи ничего не подозревающего другого бюрократа (порядок форм в стопке сохраняется. Наш чиновник теперь имеет пустую таблицу).

• Ни одна из форм не обрабатывается. Никогда. Все формы постоянно циркулируют между бюрократами.

Вам следует промоделировать этот механизм. Чтобы быть более точным, следует промоделировать последовательность запросов, каждый из которых либо “бюрократ B получает новую форму F”, либо “бюрократ B[1] отдает все свои формы бюрократу B[2]”. Считайте, что в начале моделирования ни у кого не было ни одной формы.

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

Содержит не более 10^5 + 1 строк. Каждая строка имеет один из следующих форматов:

• “A b f”, где b - ID бюрократа, f - ID новой формы, которая добавляется на верх кипы.

• “M b[1] b[2]”, где b[1] и b[2] - ID таких бюрократов, что все формы со стола b[1] переносятся на верх кипы на столе b[2] (если стол b[1] пуст, но ничего не происходит).

• “E” - завершение моделирования. Эта строка встречается только раз, она последняя на входе.

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

Рассмотрим всех бюрократов, чьи кипы форм в конце моделирования не пусты. Для каждого из них выведите одну строку вида “id: f[1] f[2] ... f[n]”, где id - ID бюрократа, от f[1] до f[n] - ID форм в его куче сверху вниз. ID бюрократов следует выводить в возрастающем виде. Пробелы следует выводить строго в тех местах где они должны быть.

Пример

Рассмотрим порядок выполнения запросов в тесте 1:

• Бюрократ 10 получил новую форму 47.

• Бюрократ 10 отдал все свои формы (1 форму) бюрократу 20.

• Бюрократ 20 отдал все свои формы (1 форму) обратно бюрократу 10.

• Бюрократ 20 отдал все свои формы (0 форм) бюрократу 10.

• Бюрократ 20 получил новую форму 42.

• Бюрократ 20 получил новую форму 43.

• Бюрократ 20 отдал все свои формы (2 формы) бюрократу 10.

Примеры