# Partition of the set

# Partition of the set

Consider a set consisting of the first **n** natural numbers: **N _{n}** = {

**1**,

**2**, ...,

**n**}. Partition - a representation of this set as the union of one or more non-empty sets. Examples of partitions for

**n**=

**5**are:

{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}

In total there are **52** partitions of **N _{5}**. Note that the partitions that differ only by order of the merged sets did not differ.

Partition of the set **N _{n}** can be ordered

*lexicographically*.

In order to determine the order, first define the lexicographic order on subsets of **N _{n}**. We say that a set

**A**

**N**lexicographically less than the set

_{n}**B**

**N**and write

_{n}**A**<

**B**, if one of the following statements:

- There exists
**i**, such that**i****A**,**i****B**, for all**j**<**i**:**j****A**iff**j****B**, and there is a**k**>**i**, such that**k****B**; **A****B**and**i**<**j**for all**i****A**and**j****B**\**A**.

It is obvious that this relation is a total order on subsets of **N _{n}**. Now we define the canonical representation of the partition as a representation in that combines multiple lexicographically.

Partitions are ordered lexicographically as follows. Partition of**N _{n}** =

**A**U

_{1}**A**U

_{2}**...**U

**A**lexicographically less than the partition of

_{k}**N**=

_{n}**B**U

_{1}**B**U

_{2}**...**U

**B**, if there is an

_{l}**i**, as

**A**=

_{1}**B**,

_{1}**A**=

_{2}**B**, ...,

_{2}**A**=

_{i-1}**B**and

_{i-1}**A**<

_{i}**B**.

_{i}According to the partition of **N _{n}** find the following in the lexicographic order decomposition.

**Input**

The input file contains several descriptions of the tests. Each description is the canonical representation of the partition. The first line contains the description of **n** and **k** - number of elements in the partitions the set and the number of parts in a partition (**1** ≤ **n** ≤ **200**). Subsequent **k** rows contain elements of the partition. Elements of each set in ascending order.

Describe the tests are separated by blank lines. The last line of input contains two zero. This test should not be handled.

Sum of **n** over all the descriptions do not exceed **2000**.

**Output**

For each test, the following output in lexicographic order decomposition. If the partition in the input file is the latest in leksigoraficheskom order, display the first in lexicographic order. Use the same format as the input file. Separate partitions from each other by blank lines.

5 2 1 2 3 4 5 5 2 1 3 5 2 4 5 1 1 2 3 4 5 5 5 1 2 3 4 5 0 0

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