Write a program that prints all the permutations of { 1, …, *n* }
with *k* inversions, for a given *n* and *k*.
An inversion is a pair of elements *x* and *y*
such that *x* > *y*
and such that *x* appears before *y* in the permutation.

**Input**

Input consists of two natural numbers *n* and *k*,
such that *n* ≥ 1 and 0 ≤ *k* ≤ *n*(*n* − 1)/2.

**Output**

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

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

**Hint**

Here, a very simple algorithm may be too slow.

Public test cases

**Input**

5 2

**Output**

(1,2,4,5,3) (1,2,5,3,4) (1,3,2,5,4) (1,3,4,2,5) (1,4,2,3,5) (2,1,3,5,4) (2,1,4,3,5) (2,3,1,4,5) (3,1,2,4,5)

**Input**

10 45

**Output**

(10,9,8,7,6,5,4,3,2,1)

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++