Under construction

Still being built. Things may change

N and M (11)

Interview

Time limit1sMemory limit512 MB

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

Medium4 of 10

Topics
Backtracking, Recursion, Sorting, Brute force
Solved
No attempts yet

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≤M≤N≤71 \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.

Examples3

  1. Example 1

    Input
    3 1
4 4 2
    Expected output
    2
4

  2. Example 2

    Input
    4 2
9 7 9 1
    Expected output
    1 1
1 7
1 9
7 1
7 7
7 9
9 1
9 7
9 9

  3. Example 3

    Input
    4 4
1 1 2 2
    Expected output
    1 1 1 1
1 1 1 2
1 1 2 1
1 1 2 2
1 2 1 1
1 2 1 2
1 2 2 1
1 2 2 2
2 1 1 1
2 1 1 2
2 1 2 1
2 1 2 2
2 2 1 1
2 2 1 2
2 2 2 1
2 2 2 2