N and M (3)

Interview

Time limit1sMemory limit512 MB

Summary

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

Level: Easy3 of 10
Topics: Backtracking, Recursion, Brute force, Implementation
Solved: No attempts yet

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.

Examples3

Example 1
Input
```
3 1
```
Expected output
```
1
2
3
```

Example 2

Input

4 2

Expected output

Example 3

Input

3 3

Expected output