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++