配点 : $400$ 点

問題文

$(1, 2, \dots, N)$ の順列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。 $1 \leq L \leq R \leq N$ を満たす整数の組 $(L, R)$ に対して、$A$ の $L$ 番目から $R$ 番目までの要素を反転してできる順列を $f(L, R)$ とします。 ここで、「$A$ の $L$ 番目から $R$ 番目までの要素を反転する」とは、$A_L, A_{L+1}, \dots, A_{R-1}, A_R$ を $A_R, A_{R-1}, \dots, A_{L+1}, A_{L}$ に同時に置き換えることを言います。

$(L, R)$ を $1 \leq L \leq R \leq N$ を満たすように選ぶ方法は $\frac{N(N + 1)}{2}$ 通りあります。 このような $(L, R)$ の組全てに対して順列 $f(L, R)$ をすべて列挙して辞書順にソートしたときに、先頭から $K$ 番目にある順列を求めてください。

制約

• $1 \leq N \leq 7000$
• $1 \leq K \leq \frac{N(N + 1)}{2}$
• $A$ は $(1, 2, \dots, N)$ の順列

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$A_1$ $A_2$ $\dots$ $A_N$

出力

順列 $f(L, R)$ を列挙して辞書順にソートしたときに、先頭から $K$ 番目にある順列を $B =(B_1, B_2, \dots, B_N)$ とする。 このとき以下の形式で $B$ を出力せよ。

$B_1$ $B_2$ $\dots$ $B_N$

3 5
1 3 2

2 3 1

$1 \leq L \leq R \leq N$ を満たす $(L, R)$ の組全てに対して順列 $f(L, R)$ をすべて列挙すると次のようになります。

• $f(1, 1) = (1, 3, 2)$
• $f(1, 2) = (3, 1, 2)$
• $f(1, 3) = (2, 3, 1)$
• $f(2, 2) = (1, 3, 2)$
• $f(2, 3) = (1, 2, 3)$
• $f(3, 3) = (1, 3, 2)$

これらを辞書順にソートしたときに $5$ 番目に来る順列は $f(1, 3) = (2, 3, 1)$ です。よってこれを出力します。

5 15
1 2 3 4 5

5 4 3 2 1

答えは $f(1, 5)$ です。

10 37
9 2 1 3 8 7 10 4 5 6

9 2 1 6 5 4 10 7 8 3