N and M (7)

Given N distinct numbers and a length M, print every length-M sequence drawn from the numbers with repetition allowed, deduplicated and in increasing lexicographic order.

Medium4BacktrackingRecursionSortingBrute 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$ satisfying the conditions below.

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

Input

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

The second line contains the $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. Do not print the same sequence more than once, and separate the numbers of a sequence with a space.

Print the sequences in increasing lexicographic order. Two sequences are ordered by comparing their values position by position, starting from the first element.