N and M (9)

Interview

Time limit1sMemory limit512 MB

Summary

Given N numbers (with duplicates) and length M, print every distinct length-M selection in increasing lexicographic order, using each copy at most once.

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 you can build by choosing M of the given N numbers.

The same number can be given several times, and each number can be used only as many times as it is given.

Input

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

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

Output

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

Print the sequences in increasing lexicographic order. Two sequences are compared element by element from the front, by numeric value.

Examples3

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

Example 2

Input

4 2
9 7 9 1

Expected output

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