N and M (6)

Interview

Time limit1sMemory limit512 MB

Summary

Given N distinct natural numbers and M, print every ascending M-element subsequence in lexicographic order without repeats.

Level: Easy3 of 10
Topics: Backtracking, Sorting, Recursion, Brute force
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$ that satisfies the conditions below. The $N$ natural numbers are all different.

the sequence consists of $M$ numbers chosen from the given $N$ natural numbers
the chosen sequence is in ascending order

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 less than or equal to 10,000.

Output

Print one sequence that satisfies the conditions per line. Do not print the same sequence twice, and separate the elements 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
```
1 7
1 8
1 9
7 8
7 9
8 9
```

Example 3

Input

4 4
1231 1232 1233 1234

Expected output

1231 1232 1233 1234