Length M sequences from N numbers

Interview

Time limit1sMemory limit512 MB

Summary

Given N distinct numbers and an M, print every length-M permutation of the numbers in lexicographic order without repeats.

Level: Easy3 of 10
Topics: Backtracking, Recursion, Sorting, Brute force
Solved: No attempts yet

Problem

You are given N distinct natural numbers and a natural number M. Write a program that finds every sequence of length M you can build by choosing M of those N numbers and writing them in a row.

You cannot choose the same number twice.
Two sequences that hold the same numbers in a different order are different sequences.

Input

The first line contains N and M. (1 ≤ M ≤ N ≤ 8)

The second line contains N numbers. Every given number is a natural number no greater than 10,000, and all of them are different.

Output

Print one sequence that satisfies the condition per line. Separate the elements of a sequence with a space. Do not print the same sequence twice.

Print the sequences in increasing lexicographic order. Compare two sequences element by element from the front, by the value of the numbers.

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 1232 1233 1234
1231 1232 1234 1233
1231 1233 1232 1234
1231 1233 1234 1232
1231 1234 1232 1233
1231 1234 1233 1232
1232 1231 1233 1234
1232 1231 1234 1233
1232 1233 1231 1234
1232 1233 1234 1231
1232 1234 1231 1233
1232 1234 1233 1231
1233 1231 1232 1234
1233 1231 1234 1232
1233 1232 1231 1234
1233 1232 1234 1231
1233 1234 1231 1232
1233 1234 1232 1231
1234 1231 1232 1233
1234 1231 1233 1232
1234 1232 1231 1233
1234 1232 1233 1231
1234 1233 1231 1232
1234 1233 1232 1231