N and M (9)

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

Medium4BacktrackingSortingRecursionInterviewNo attempts yetTime limit1sMemory limit512 MB

Description

Examples3

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.