MMINPER - Minimum Permutation

The inversion number of an integer sequence a1, a2 ... an is the number of pairs (ai, aj) that satisfy i < j and ai > aj . Given n and the inversion number m, your task is to find the smallest permutation of the set { 1, 2 ... n } , whose inversion number is exactly m. A permutation a1, a2 ... an is smaller than b1, b2 ... bn if and only if there exists an integer k such that aj = bj for 1 ≤ j < k but ak < bk.

Input

The input consists of several test cases. Each line of the input contains two integers n and m. Both of the integers at the last line of the input is −1, which should not be processed. You may assume that 1 ≤ n ≤ 50000 and 0 ≤ m ≤ 1/2n(n − 1).

Output

For each test case, print a line containing the smallest permutation as described above, separates the numbers by single spaces.

Sample

Input
5 9
7 3
-1 -1

Output
4 5 3 2 1
1 2 3 4 7 6 5

Added by:psetter
Date:2009-02-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Pre Shanghai 2004

hide comments
2023-09-15 05:16:44
N=7:
K= 0: 1 2 3 4 5 6 7
K= 1: 1 2 3 4 5 7 6
K= 2: 1 2 3 4 6 7 5
K= 3: 1 2 3 4 7 6 5
K= 4: 1 2 3 5 7 6 4
K= 5: 1 2 3 6 7 5 4
K= 6: 1 2 3 7 6 5 4
K= 7: 1 2 4 7 6 5 3
K= 8: 1 2 5 7 6 4 3
K= 9: 1 2 6 7 5 4 3
K=10: 1 2 7 6 5 4 3
K=11: 1 3 7 6 5 4 2
K=12: 1 4 7 6 5 3 2
K=13: 1 5 7 6 4 3 2
K=14: 1 6 7 5 4 3 2
K=15: 1 7 6 5 4 3 2
K=16: 2 7 6 5 4 3 1
K=17: 3 7 6 5 4 2 1
K=18: 4 7 6 5 3 2 1
K=19: 5 7 6 4 3 2 1
K=20: 6 7 5 4 3 2 1
K=21: 7 6 5 4 3 2 1
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.