Length M sequences from N numbers

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

Easy3BacktrackingRecursionSortingBrute forceInterviewNo attempts yetTime limit1sMemory limit512 MB

Description

Examples3

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.