問題文

(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 を求めてください。

制約

• 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) の順列
• 入力はすべて整数

入力例 1

3
2 3 1
3 2 1

出力例 1

2 1 3

操作によって 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)

入力例 2

4
4 2 1 3
2 1 3 4

出力例 2

2 4 1 3

操作によって 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)

入力例 3

4
1 2 3 4
1 2 3 4

出力例 3

1 2 3 4

一度も操作を行いません。