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

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

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

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

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

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

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

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

• “**A b f**”, где b - ID бюрократа, f - ID новой формы, которая добавляется на верх кипы.
• “Mb1b2”, где b1 и b2 - ID таких бюрократов, что все формы со стола b1 переносятся на верх кипы на столе b2 (если стол b1 пуст, но ничего не происходит).
• “E” - завершение моделирования. Эта строка встречается только раз, она последняя на входе.

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

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

Пример

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

• Бюрократ 10 получил новую форму 47.
• Бюрократ 10 отдал все свои формы (1 форму) бюрократу 20.
• Бюрократ 20 отдал все свои формы (1 форму) обратно бюрократу 10.
• Бюрократ 20 отдал все свои формы (0 форм) бюрократу 10.
• Бюрократ 20 получил новую форму 42.
• Бюрократ 20 получил новую форму 43.
• Бюрократ 20 отдал все свои формы (2 формы) бюрократу 10.