配点 : $700$ 点

問題文

$(0,1,\cdots,N-1)$ の順列 $P=(P_0,P_1,\cdots,P_{N-1})$ が与えられます．

整数 $a,b$ ($0 \leq a,b \leq N-1$) に対して，順列 $f(a,b)$ を次のように定義します．

• $f(a,b)=(q_0,q_1,\cdots,q_{N-1})$ とおいて，$q_{(i+a \pmod N)}=(P_i+b \pmod N)$ ($0 \leq i \leq N-1$) と定める．

すべての $a,b$ に対し $f(a,b)$ を求めると，$N^2$ 個の順列が得られます． これらの順列を辞書順でソートすることを考えます． ソートしたあと，先頭から $K$ 番目に位置している順列を求めてください．

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq N^2$
• $(P_0,P_1,\cdots,P_{N-1})$ は $(0,1,\cdots,N-1)$ の順列である．
• 入力される値はすべて整数である

入力

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

$N$ $K$

$P_0$ $P_1$ $\cdots$ $P_{N-1}$

出力

答えとなる順列を，要素を空白区切りで出力せよ．

2 2
0 1

0 1

$f(a,b)$ として以下の $4$ つが考えられます．

• $f(0,0)=(0,1)$
• $f(0,1)=(1,0)$
• $f(1,0)=(1,0)$
• $f(1,1)=(0,1)$

これらの順列を辞書順に並べると，$(0,1),(0,1),(1,0),(1,0)$ となります． よって，この中で $2$ 番目に位置する $(0,1)$ が答えになります．

4 6
0 2 1 3

1 2 0 3

10 79
6 5 9 8 7 1 3 2 0 4

7 9 8 2 1 0 4 6 5 3