Write a program to print all the permutations of {1, …, n} with exactly k cycles, where 1 ≤ k ≤ n. For exemple, consider the permutation (4, 3, 2, 5, 1, 7, 6). At position 1 there is a 4, at position 4 there is a 5, and at position 5 there is a 1. Therefore, one of the cycles is 1 → 4 → 5 → 1. The other two cycles are 2 → 3 → 2 and 6 → 7 → 6. The permutation (3,2,1) has the two cycles 1 → 3 → 1 and 2 → 2, and the permutation (3,4,5,6,7,1,2) only has the cycle 1 → 3 → 5 → 7 → 2 → 4 → 6 → 1.

Input

Input consists of n and k, with 1 ≤ k ≤ n.

Output

Print all the permutations of {1, …, n} with k cycles.

You can print the solutions to this exercise in any order.

Hint

A possible program does not build the permutations consecutively from left to right, but jumping over the solution, using a function

void f(int i, int ini, int cells, int cycles);

where *i* is the next cell to fill,
*ini* is where the current cycle—still to be closed—starts,
*cells* is the number of cells still free,
and *cycles* is the number of cycles yet to be created.

Public test cases

**Input**

3 1

**Output**

(2, 3, 1) (3, 1, 2)

**Input**

3 2

**Output**

(2, 1, 3) (1, 3, 2) (3, 2, 1)

**Input**

3 3

**Output**

(1, 2, 3)

Information

- Author
- Enric Rodríguez
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++