N and M (12)

Interview

Time limit2sMemory limit512 MB

Summary

Given N numbers and a length M, list all non-decreasing length-M sequences drawn from the numbers with repetition, in lexicographic order.

Level: Medium4 of 10
Topics: Backtracking, Sorting, Recursion, Implementation
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 sequence is made by choosing $M$ of the given $N$ numbers.
You may choose the same number more than once.
The sequence is non-decreasing. A sequence $A$ of length $K$ is non-decreasing when $A_1 \le A_2 \le \cdots \le A_{K-1} \le A_K$ holds.

Input

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

The second line contains $N$ numbers. Every number given in the input is a natural number no greater than 10,000.

Output

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

Print the sequences in increasing lexicographic order.

Examples3

Example 1
Input
```
3 1
4 4 2
```
Expected output
```
2
4
```
Example 2
Input
```
4 2
9 7 9 1
```
Expected output
```
1 1
1 7
1 9
7 7
7 9
9 9
```

Example 3

Input

4 4
1 1 2 2

Expected output