Приданое

Стрела старшего сына на боярский двор упала, и подняла ее боярская дочь. Приехал он с обозом подарков, а уехал с обозом приданого.

Боярин - человек хозяйственный, все вещи у него инвентарные номера имеют. Инвентарные номера хитрые: первые три цифры в них означают, к какой категории вещь относится - то ли это одежда праздничная, то ли утварь столовая. Следующие три цифры - материал, из которого вещь сделана (парча ли, дерево ли, золото ли). Дальше четыре цифры - год приобретения, за ними еще две - месяц приобретения. За ними три цифры показывают, где у вещи место хранения. Потом три цифры идут - означают, кто владельцем вещи считается. А последние четыре цифры нумеруют вещи одной категории.

Три дня составляли для дочки список - что ей с собой взять надобно: то одно вспомнят, то другое. Потому в списке инвентарные номера совсем не по порядку идут. Пока по горам обратно ехали, невеста надумала: «У батюшки моего свой порядок был, и у меня свой будет». Потому, как только обоз на отдых остановился, велит порядок в каждой телеге навести: сложить рядом вещи из одной категории.

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

Наводить порядок стали так. Выкладывают все вещи из телеги в ряд - одну за другой (хозяйка рядом стоит, проверяет - у нее по каждой телеге список есть, в том порядке, в каком складывали).

Затем поступают следующим образом. Идут вдоль выложенных вещей (от начала списка). Если, допустим, на месте № j находится вещь из категории, уже встречавшейся раньше, то ее берут и относят к предыдущей вещи этой же категории, чтобы положить справа. Но место справа необходимо освободить. Вещь, занимающую это место (но принадлежащую другой категории), перемещают на место принесенной - т.е. на место № j. После этого обмена местами просмотр вещей продолжается - со следующей за только что перемещенной вещью (с места № j+1). Когда добираются до последней вещи, возвращаются к самой первой - чтобы пройти вновь, и, если понадобится, переложить еще какие-то вещи...

Процесс продолжается до тех пор, пока все вещи не окажутся разложенными по категориям.

Ваша задача - вывести содержимое телег после такого перекладывания.

Примечание. Проиллюстрируем процесс перекладывания. Пусть есть одна телега и три категории вещей - обозначим их A, B, C. Ради краткости не будем писать инвентарные номера полностью, а ограничимся их «модельным представлением» - натуральными числами. Тогда, если исходный ряд вещей имеет следующий вид:

A1 A2 B1 C1 A3 B2 B3 A4 C2 C3 B4 A5 C4

то в перекладывание будет происходить следующим образом:

1) сначала обменяются местами A3 и B1:

A1 A2 A3 C1 B1 B2 B3 A4 C2 C3 B4 A5 C4

Просмотр продолжится с B2

2) обменяются местами A4 и С1

A1 A2 A3 A4 B1 B2 B3 C1 C2 C3 B4 A5 C4

Просмотр продолжится с C2

3) обменяются местами B4 и C1

A1 A2 A3 A4 B1 B2 B3 B4 C2 C3 C1 A5 C4

4) обменяются местами A5 и B1

A1 A2 A3 A4 A5 B2 B3 B4 C2 C3 C1 B1 C4

5) обменяются местами C4 и B1

A1 A2 A3 A4 A5 B2 B3 B4 C2 C3 C1 C4 B1

На этом первый проход по ряду вещей будет завершен - поскольку просмотр следовало бы продолжить, начиная с вещи, которая следует за B1, но такой не находится.

6) Теперь следует вернуться к началу ряда и пройти по нему вновь. На этот раз никаких обменов не будет производиться, пока не будет найдена лежащая не на «своем» месте вещь B1. Ее придется поменять местами с C2.

A1 A2 A3 A4 A5 B2 B3 B4 B1 C3 C1 C4 C2

Вновь просматривая ряд вещей, можно установить, что больше никаких перемещений не требуется: вещи разложены по категориям.

Формат входного файла

Первая строка - целое число N (1 <= N <= 20) - количество телег в обозе

В каждой из следующих N строк записана информация о содержимом очередной телеги. Так, в строке № j+1, описывающей телегу № j, сначала указано целое число Mj - количество вещей в телеге (1< = Mj <= 100), а затем через пробел Mj инвентарных номеров согласно описанию - каждый из 22 цифр.

Формат выходного файла

N строк, строка №j содержит через пробел инвентарные номера вещей в телеге № j после перекладывания согласно условию задачи.

Пример входного файла

1

3 1013451083112650010015 2130961064011370030087 1011231092031140120153

Пример выходного файла

1013451083112650010015 1011231092031140120153 2130961064011370030087