Arrangements Without Steep Descents

Interview

Time limit1sMemory limit1024 MB

Summary

Print every ordered selection of k distinct numbers from 1 to n where no adjacent pair drops by more than 1, sorted lexicographically.

Level: Medium4 of 10
Topics: Backtracking, Combinatorics
Solved: No attempts yet

Problem

An arrangement of $n$ taken $k$ at a time is an array $a[1..k]$ of $k$ distinct natural numbers, each between $1$ and $n$ .

A pair of adjacent elements $a[i], a[i+1]$ is a descent if $a[i] > a[i+1]$ . A descent is steep if $a[i] > a[i+1] + 1$ .

Given $n$ and $k$ , print all arrangements of $n$ taken $k$ at a time that have no steep descents. Sort the arrangements by the first element, then by the second element when the first is equal, then by the third, and so on.

Input

The first line contains a natural number $n$ . The second line contains a natural number $k$ ( $1 \le k \le n \le 13$ ).

Output

Print all arrangements of $n$ taken $k$ at a time without steep descents, one per line. Separate the numbers within an arrangement with spaces.

Examples1

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