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_n lexicographically less than the set B N_n and write 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_1 U A_2 U ... U A_k lexicographically less than the partition of N_n = B_1 U B_2 U ... U B_l, if there is an i, as A_1 = B_1, A_2 = B_2, ..., A_{i-1} = B_{i-1} and 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.