Розбиття множини
Розглянемо множину, яка складається з перших n натуральних чисел: N_n = {1, 2, ..., n}. Розбиття - це подання цієї множини у вигляді об'єднання однієї чи декількох непорожніх множин. Прикладами розбиття для n=5 є:
{1, 2, 3, 4, 5} = {1, 2, 3} U {4, 5}
{1, 2, 3, 4, 5} = {1, 3, 5} U {2, 4}
{1, 2, 3, 4, 5} = {1, 2, 3, 4, 5}
{1, 2, 3, 4, 5} = {1} U {2} U {3} U {4} U {5}
Всього існує 52 розбиття множини N_5. Відмітимо, що розбиття, які відрізняються лише порядком об'єднуваних множин, не відрізняються.
Розбиття множини N_n можна впорякувати лексикогріфчно.
Для того, щоб визначити цей порядок, спочатку визначимо лексикографічний порядок на підмножинах N_n. Будемо казати, що множина A N_n лексикографічно менше множини B N_n і записувати A < B, якщо вірно одне з наступних тверджень:
знайдеться i, таке що i
A, i
B, для всіх j < i: j
A iff j
B, і знайдеться k > i, таке що k
B;
A
B та i < j для всіх i
A и j
B A.
Очевидно, що введене відношення є повним порядком на підмножинах множини N_n. Тепер визначимо канонічне подання розбиття, як подання, у якому об'єднувані множини впорядковані лексикографічно.
Разбиття впорядковуються лексикографічно наступним чином. Розбиття N_n = A_1 U A_2 U ... U A_k лексикографічно менше розбиття N_n = B_1 U B_2 U ... U B_l, якщо існує таке i, що A_1 = B_1, A_2 = B_2, ..., A_{i-1} = B_{i-1} і A_i < B_i.
За розбиття множини N_n знайдіть наступне у лексикографічному порядку розбиття.
Вхідні дані
Вхідний файл містить декілька описів тестів. Кажен опис є канонічним поданням розбиття. Перший рядок опису містить n і k — кількість елементів у множині, що розбивається, і кількість частин у розбитті (1 ≤ n ≤ 200). Наступні k рядків містять елементи розбиття. Елементи кожної множини впорядковані за зростанням.
Опии тестів відокремлено один від одного порожніми рядками. Останній рядок вхідного файлу містить два нулі. Цей тест не повинен опрацьовуватись.
Сума n по всім описам не перевищує 2000.
Вихідні дані
Для кожного тесту виведіть наступну у лексикографічному порядку розбиття. Якщо розбиття у вхідному файлі є оствннім у лексигорафічному порядку, виведіть перше у лексикографісному порядку. Використовуйте той же формат, що і у вхідному файлі. Відокремлюйте розбиття одне від одного порожніми рядками.