Partition of the set#1329

Partition of the set

1 second

64 megabytes

Hard

Consider a set consisting of the first $n$ natural numbers: $N_{n} = {1, 2, \dots, n}$ N_n = \{1, 2, \ldots, n\}. A partition is a representation of this set as the union of one or more non-empty sets. Examples of partitions for $n = 5$ n = 5 are:

{1, 2, 3, 4, 5} = {1, 2, 3} \cup {4, 5}

\{1, 2, 3, 4, 5\} = \{1, 2, 3\} \cup \{4, 5\}

{1, 2, 3, 4, 5} = {1, 3, 5} \cup {2, 4}

\{1, 2, 3, 4, 5\} = \{1, 3, 5\} \cup \{2, 4\}

{1, 2, 3, 4, 5} = {1, 2, 3, 4, 5}

\{1, 2, 3, 4, 5\} = \{1, 2, 3, 4, 5\}

{1, 2, 3, 4, 5} = {1} \cup {2} \cup {3} \cup {4} \cup {5}

\{1, 2, 3, 4, 5\} = \{1\} \cup \{2\} \cup \{3\} \cup \{4\} \cup \{5\}

In total, there are $52$ partitions of $N_{5}$ N_5. Note that partitions that differ only by the order of the merged sets are not considered different.

Partitions of the set $N_{n}$ N_n can be ordered lexicographically.

To define this order, first set the lexicographic order on subsets of $N_{n}$ N_n. We say that a set $A \subset N_{n}$ A \subset N_n is lexicographically less than the set $B \subset N_{n}$ B \subset N_n (written $A ≺ B$ A \prec B), if one of the following statements holds:

There exists $i$ such that $i \in A$ i \in A, $i \in / B$ i \notin B and for all $j < i$ j < i, $j \in A$ j \in A if and only if $j \in B$ j \in B, and there exists $k < i$ k < i such that $k \in / A$ k \notin A, $k \in B$ k \in B;
$A \subset B$ A \subset B and $i < j$ i < j for all $i \in A$ i \in A and $j \in B ∖ A$ j \in B \setminus A.

It is clear that this relation is a total order on the subsets of $N_{n}$ N_n. Now we define the canonical representation of a partition as a representation where the merged sets are sorted lexicographically.

Partitions are ordered lexicographically as follows. A partition $N_{n} = A_{1} \cup A_{2} \cup \dots \cup A_{k}$ N_n = A_1 \cup A_2 \cup \ldots \cup A_k is lexicographically less than a partition $N_{n} = B_{1} \cup B_{2} \cup \dots \cup B_{l}$ N_n = B_1 \cup B_2 \cup \ldots \cup B_l, if there exists such $i$ that $A_{1} = B_{1}$ A_1 = B_1, $A_{2} = B_{2}$ A_2 = B_2, ..., $A_{i - 1} = B_{i - 1}$ A_{i-1} = B_{i-1} and $A_{i} ≺ B_{i}$ A_i \prec B_i.

Given a partition of the set $N_{n}$ N_n, find the next partition in lexicographic order.

Input

The input file contains several test descriptions. Each description is the canonical representation of a partition. The first line of a description contains $n$ and $k$ — the number of elements in the set and the number of parts in the partition ( $1 \leq n \leq 200$ 1 \leq n \leq 200). The next $k$ lines contain the elements of the partition. The elements of each set are sorted in ascending order.

Test descriptions are separated by blank lines. The last line of the input file contains two zeros. This test should not be processed.

The sum of $n$ over all descriptions does not exceed $2000$ .

Output

For each test, output the next partition in lexicographic order. If the partition in the input file is the last in lexicographic order, output the first in lexicographic order. Use the same format as the input file. Separate partitions from each other by blank lines.

Examples

Example 1

Loading

N_{n} = {1, 2, \dots, n}

n = 5

{1, 2, 3, 4, 5} = {1, 2, 3} \cup {4, 5}

{1, 2, 3, 4, 5} = {1, 3, 5} \cup {2, 4}

{1, 2, 3, 4, 5} = {1, 2, 3, 4, 5}

{1, 2, 3, 4, 5} = {1} \cup {2} \cup {3} \cup {4} \cup {5}

N_{5}

N_{n}

N_{n}

A \subset N_{n}

B \subset N_{n}

A ≺ B

i \in A

i \in / B

j < i

j \in A

j \in B

k < i

k \in / A

k \in B

A \subset B

i < j

i \in A

j \in B ∖ A

N_{n}

N_{n} = A_{1} \cup A_{2} \cup \dots \cup A_{k}

N_{n} = B_{1} \cup B_{2} \cup \dots \cup B_{l}

A_{1} = B_{1}

A_{2} = B_{2}

A_{i - 1} = B_{i - 1}

A_{i} ≺ B_{i}

N_{n}

1 \leq n \leq 200