N and M (4)

Print all non-decreasing sequences of length M chosen from 1 to N, each exactly once, in lexicographic order.

Easy3BacktrackingRecursionInterviewNo attempts yetTime limit1sMemory limit512 MB

Description

Examples3

Problem

Given natural numbers N and M, write a program that finds every sequence of length M that satisfies the conditions below.

A sequence made of M numbers chosen from the natural numbers 1 to N
The same number may be chosen more than once.
The chosen sequence must be non-decreasing.
- A sequence A of length K is non-decreasing if it satisfies $A_1 \le A_2 \le \cdots \le A_{K-1} \le A_K$ .

Input

The first line contains the natural numbers N and M. ( $1 \le M \le N \le 8$ )

Output

Print one sequence that satisfies the conditions per line. Do not print the same sequence twice, and separate the elements of each sequence with a space.

Print the sequences in increasing lexicographic order.