N and M (11)

Given N numbers and a length M, list every length-M sequence drawn from the numbers, allowing repeats, in increasing lexicographic order without duplicates.

Medium4BacktrackingRecursionSortingBrute forceInterviewNo 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 that satisfies the conditions below.

The sequence is made of M numbers chosen from the given N numbers.
The same number may be chosen more than once.

Input

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

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 per line. Separate the numbers inside a sequence with a space. Do not print the same sequence twice.

Print the sequences in increasing lexicographic order.