N and M (8)

Time limit1sMemory limit512 MB

Summary

Given N distinct natural numbers and a length M, print all non-decreasing sequences of length M drawn from the numbers, in lexicographic order.

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

Problem

You are given N natural numbers and a natural number M. Write a program that finds every sequence of length $M$ satisfying all of the conditions below. The N natural numbers are all different.

a sequence of M numbers chosen from the N natural numbers
the same number may be chosen more than once.
the chosen sequence must be non-decreasing.
- a sequence $A$ of length $K$ is non-decreasing if it satisfies $A_1 \le A_2 \le \dots \le A_{K-1} \le A_K$ .

Input

The first line contains $N$ and $M$ . ( $1 \le M \le N \le 8$ )

The second line contains $N$ numbers. Every number in the input is a natural number less than or equal to 10,000.

Output

Print one sequence satisfying the conditions per line. Do not print the same sequence more than once, and separate the numbers of each sequence with a space.

Print the sequences in increasing lexicographic order.

Examples3

Example 1
Input
```
3 1
4 5 2
```
Expected output
```
2
4
5
```

Example 2

Input

4 2
9 8 7 1

Expected output

Example 3

Input

4 4
1231 1232 1233 1234

Expected output

1231 1231 1231 1231
1231 1231 1231 1232
1231 1231 1231 1233
1231 1231 1231 1234
1231 1231 1232 1232
1231 1231 1232 1233
1231 1231 1232 1234
1231 1231 1233 1233
1231 1231 1233 1234
1231 1231 1234 1234
1231 1232 1232 1232
1231 1232 1232 1233
1231 1232 1232 1234
1231 1232 1233 1233
1231 1232 1233 1234
1231 1232 1234 1234
1231 1233 1233 1233
1231 1233 1233 1234
1231 1233 1234 1234
1231 1234 1234 1234
1232 1232 1232 1232
1232 1232 1232 1233
1232 1232 1232 1234
1232 1232 1233 1233
1232 1232 1233 1234
1232 1232 1234 1234
1232 1233 1233 1233
1232 1233 1233 1234
1232 1233 1234 1234
1232 1234 1234 1234
1233 1233 1233 1233
1233 1233 1233 1234
1233 1233 1234 1234
1233 1234 1234 1234
1234 1234 1234 1234