AT_tupc2022_h Next Permutation

$ (1,2,\ldots,N) $ の順列を以下では単に順列と呼びます。 順列 $ P $ に対して、順列 $ \mathrm{NextPermutation} (P) $ を次で定めます。 - $ P=(N,N-1,\ldots,2,1) $ のとき $ (1,2,\ldots,N-1,N) $ - そうでないとき、長さ $ N $ の順列全てを辞書順昇順に並べたときに $ P $ の次に来るもの $ 2 $ つの順列 $ P=(P_1, P_2, \ldots,P_N), Q=(Q_1, Q_2, \ldots, Q_N) $ が与えられます。 $ P $ が $ (1,2,\ldots, N-1,N) $ に一致するまで、次の操作を繰り返します。 - $ P $ を $ \mathrm{NextPermutation} (P) $ で、 $ Q $ を $ \mathrm{NextPermutation} (Q) $ で置き換える。 最終的な $ Q $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $ $ Q_1 $ $ Q_2 $ $ \ldots $ $ Q_N $

求める順列を $ Q'=(Q'_1,Q'_2,\ldots,Q'_N) $ として、 $ Q'_1,Q'_2,\ldots,Q'_N $ をこの順に空白区切りで一行に出力せよ。

### Sample Explanation 1 操作によって $ P,Q $ は以下のように変化します。 - $ P $ ： $ (2,3,1)\to (3,1,2)\to (3,2,1)\to (1,2,3) $ - $ Q $ ： $ (3,2,1)\to (1,2,3)\to (1,3,2)\to (2,1,3) $ ### Sample Explanation 2 操作によって $ P,Q $ は以下のように変化します。 - $ P $ ： $ (4,2,1,3)\to (4,2,3,1)\to (4,3,1,2)\to (4,3,2,1)\to(1,2,3,4) $ - $ Q $ ： $ (2,1,3,4)\to(2,1,4,3)\to(2,3,1,4)\to(2,3,4,1)\to(2,4,1,3) $ ### Sample Explanation 3 一度も操作を行いません。 ### Constraints - $ 2\leq N\leq 2\times 10^5 $ - $ (P_1, P_2, \ldots,P_N),(Q_1, Q_2, \ldots, Q_N) $ は $ (1,2,\ldots,N) $ の順列 - 入力はすべて整数