N and M (3)

Print every length-M sequence from 1 to N in lexicographic order, allowing repeats.

Easy3BacktrackingRecursionBrute forceImplementationInterviewNo attempts yetTime limit1sMemory limit512 MB

Description

Examples3

Problem

You are given two natural numbers $N$ and $M$ . Write a program that finds every sequence of length $M$ formed by choosing $M$ numbers from the natural numbers 1 to $N$ .

The same number can be chosen more than once.

Input

The first line contains two natural numbers $N$ and $M$ , separated by a space. ( $1 \le M \le N \le 7$ )

Output

Print one sequence that satisfies the condition per line. Separate the elements of each sequence with a space.

Do not print the same sequence twice. Print the sequences in increasing lexicographic order.