http://acm.pku.edu.cn/JudgeOnline/problem?id=1197

У финской компании, выпускающей высокотехнологичное оборудование, имеется большой прямоугольный склад. На складе работают менеджер и рабочий. Стороны прямоугольника, изображающего склад на плане, в порядке их обхода называют левой, верхней, правой и нижней. Пол склада разделен на единичные квадраты. На плане они образуют ряды и колонки. Ряды пронумерованы целыми числами 1, 2, ..., начиная с верхней стороны, а колонки пронумерованы целыми числами 1,2,..., начиная с левой стороны.

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

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

Пусть необходимо разместить на складе контейнер с идентификационным номером k (будем называть его контейнер k). Рабочий проходит по первому ряду слева направо и ищет первый контейнер с идентификационным номером, большим чем k. Если он не находит такого контейнера, то контейнер k устанавливается непосредственно после самого правого контейнера в этом ряду. Если же такой контейнер l найден, то контейнер l заменяется на контейнер k, а контейнер l размещается в следующем ряду с помощью этого же метода. Если рабочий достигает ряда, в котором нет контейнеров, то контейнер устанавливается в самом левом квадрате этого ряда.

Положим, что контейнеры 3,4,9,2,5,1 прибыли на склад именно в таком порядке. Тогда размещение контейнеров на складе будет следующим:

1 4 5
2 9
3

Между менеджером и рабочим происходит следующий диалог:

Менеджер: Контейнер 5 прибыл раньше контейнера 4?

Рабочий: Нет, это невозможно.

Менеджер: О! Так ты можешь восстановить последовательность прибытия контейнеров по их расположению!

Рабочий: Вообще-то нет. Например, последовательность поступления контейнеров, которые сейчас находятся на складе, могла быть 3,2,1,4,9,5, либо 3,2,1,9,4,5, либо еще какая-нибудь из оставшихся 14 вариантов.

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

ВХОД

Входной файл имеет имя depot.in. Первая строка этого файла содержит единственное целое число R: количество рядов, в которых есть контейнеры. Последующие R строк содержат информацию о рядах 1, ..., R. Первым в каждой из этих строк находится число M: количество контейнеров в ряду. Затем в этой строке следуют M целых чисел: идентификационные номера контейнеров в ряду слева направо. Все идентификационные номера контейнеров I удовлетворяют ограничению 1 ≤ I ≤ 50.

Обозначим общее количество контейнеров на складе через N, 1 ≤ N ≤ 13.

ВЫХОД

Выходной файл имеет имя depot.out. Выходной файл содержит столько строк, сколько существует возможных различных последовательностей поступления контейнеров. Каждая из этих строк содержит N целых чисел - идентификационные номера контейнеров в возможной последовательности прибытия. Каждая строка описывает последовательность, которая не записана ни в одной другой строке.

ПРИМЕРЫ ВХОДНЫХ И ВЫХОДНЫХ ФАЙЛОВ

Пример 1:
depot.in depot.out

3
3 1 4 5
2 2 9
1 3

3 2 1 4 9 5
3 2 1 9 4 5
3 4 2 1 9 5
3 2 4 1 9 5
3 2 9 1 4 5
3 9 2 1 4 5
3 4 2 9 1 5
3 4 9 2 1 5
3 2 4 9 1 5
3 2 9 4 1 5
3 9 2 4 1 5
3 4 2 9 5 1
3 4 9 2 5 1
3 2 4 9 5 1
3 2 9 4 5 1
3 9 2 4 5 1

Пример 2:
depot.in depot.out

2
2 1 2
1 3

3 1 2
1 3 2