1945 - 神庭君のテスト反省

ストーリー

神庭君は校内テストを終えた。
神庭君によると、テスト対策のおかげで基礎問題では満点を飾ることができたが、応用問題で砕け散ったらしい。
頑張った成果は出たものの、まだ上を目指したい気持ちが芽生えたらしい。
応用問題の形式は伝えてもらったので、それを解けるプログラムを作ってあげよう。

問題

順列の配列数$N$と、全体配列が辞書順で前から何番目かを表す数字$M$が与えられる。
$N$個ある順列のうち、$i$番目の順列は1から$X_i$までの順列で、最初は辞書順が最小になるようにソートされている。
$i$番目の順列を辞書順で前から$Y_i$番目の順列にした後に、各順列をソートする。
厳密には、各順列に操作をしたのちに、各順列そのものを辞書順で見て並び替えろ。
詳しくは入出力例2を見ること。

入力

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

$N$ $M$
$X_1$ $Y_1$
$X_2$ $Y_2$
...
$X_N$ $Y_N$

1行目には整数$N$、$M$が空白区切りで与えられる。
2行目から$N$行にわたって$X$,$Y$が与えられる。

出力

全ての操作を終えた後の各配列を出力せよ。
1つの配列を1行に出力する。
配列内の要素は空白で区切ること。
出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下の制約を満たす。

• $1 \leq N \leq 100$
• $1 \leq M \leq N! , 1.5*10^{18}$
• $1 \leq X_i \leq 20$
• $1 \leq Y_i \leq X_i!$

入出力例

入力例1

1 1
1 1

出力例1

1

要素数1はどう並び替えても1パターンです。

入力例2

3 2
3 2
2 1
2 2

出力例2

1 2
2 1
1 3 2