Lotto

Time limit1sMemory limit128 MB

Summary

For each set of k numbers in ascending order, print all 6-element subsets in lexicographic order, separated by blank lines.

Level: Medium4 of 10
Topics: Backtracking, Recursion, Combinatorics
Solved: No attempts yet

Problem

In the German lotto, you choose 6 distinct numbers from $\{1, 2, \ldots, 49\}$ .

One popular strategy for picking lotto numbers is to first choose $k$ numbers ( $k > 6$ ) out of the 49 to form a set $S$ , and then pick the 6 numbers only from within $S$ .

For example, if $k = 8$ and $S = \{1, 2, 3, 5, 8, 13, 21, 34\}$ , there are 28 different ways to choose 6 numbers from this set.

Given a set $S$ and $k$ , write a program that prints every way to choose 6 numbers from $S$ .

Input

The input consists of several test cases. Each test case is given on a single line. The first number on the line is $k$ ( $6 < k < 13$ ), followed by the $k$ numbers that make up the set $S$ . The elements of $S$ are given in ascending order.

The last line of the input contains a single $0$ and is not processed.

Output

For each test case, print every way to choose 6 numbers from $S$ in lexicographic order. Each way is printed on its own line as the 6 chosen numbers in ascending order, separated by single spaces.

Print one blank line between the outputs of consecutive test cases.

Examples3

Example 1

Input

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

Expected output

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

Example 2

Input

7 1 2 3 4 5 6 7
0

Expected output

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

Example 3

Input

8 1 2 3 5 8 13 21 34
0

Expected output

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34