N and M (10)

Time limit1sMemory limit512 MB

Summary

Given N numbers and an M, print every non-decreasing length-M selection of the numbers in lexicographic order without duplicates.

Level: Easy3 of 10
Topics: Backtracking, Sorting, Implementation, 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 both conditions below.

The sequence consists of $M$ numbers chosen from the given $N$ numbers.
The chosen sequence is non-decreasing. A sequence $A$ of length $K$ is non-decreasing when $A_1 \le A_2 \le \dots \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 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 elements of a sequence with spaces.

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 7
1 9
7 9
9 9
```
Example 3
Input
```
4 4
1 1 2 2
```
Expected output
```
1 1 2 2
```