Свято дівчат
Щоб відзначити 100-річчя університету Цінхуа, n дівчат планують влаштувати вечірку. Вони є експертами в співі та танцях і люблять виступати в групах. У їхньому поточному плані передбачено сцену та ряд сидінь. Коли група дівчат має співати або танцювати на сцені, вони встають зі своїх місць і йдуть на сцену. Після виступу вони повертаються на свої місця (вони не змінюються місцями, оскільки у кожної дівчини багато особистих речей на її місці).
Вони хочуть, щоб ця процедура виглядала стильно, тому для кожного виступу місця актрис повинні бути послідовними. Наприклад, якщо є 4 дівчини, і виступають дівчата 1, 2 і 4, то вони не можуть сидіти в порядку 1-2-3-4, оскільки, коли дівчата 1, 2 і 4 встають, дивно бачити не-актрису (дівчину 3), яка сидить між дівчатами 2 і 4.
Як я вже згадував, вони дуже добре співають і танцюють, тому їм вдалося придумати багато комбінацій. Тепер вони трохи стурбовані: чи є спосіб посадити всіх дівчат так, щоб вимога вище могла бути задоволена (тобто для кожної комбінації місця актрис є послідовними).
Як досвідчений програміст, ви вирішуєте (я знаю, що насправді вас просять, але...) написати програму, яка може обчислити кількість розташувань сидінь. Оскільки дівчата постійно думають про нові комбінації, ваша програма повинна вміти читати нові комбінації і відповідно коригувати відповідь. Коли є лише кілька можливих розташувань (тобто не більше k можливих рішень), ваша програма повинна вивести всі з них.
Вхідні дані
Є кілька тестових випадків. Перша строка містить три цілі числа n, m, k (1 ≤ n, m, k ≤ 200), де n — це кількість дівчат, m — це кількість комбінацій, а k — це параметр, описаний вище. Кожна з наступних m строк містить набір цілих чисел, завершених нулем. Ці цілі числа є ID дівчат у комбінації (дівчата пронумеровані від 1 до n). Вхід завершується кінцем файлу (EOF). Розмір вхідного файлу не перевищує 1 МБ.
Вихідні дані
Для кожної нової комбінації виведіть кількість розташувань сидінь, після врахування цієї комбінації. Якщо немає способу, виведіть 0 і ігноруйте комбінацію. Якщо є не більше k способів, виведіть їх по одному в рядку, в лексикографічному порядку.