AT_awtf2026algo_d Adj Swap Lex Max

$ (1,2,\ldots,N) $ の順列 $ P $ 及び $ Q $ が与えられます． ここで $ P $ は辞書順で $ Q $ 以下です． あなたは以下の操作を $ 0 $ 回以上行うことができます． - $ P $ の隣接する $ 2 $ 要素を選んで入れ替える．ただしこの時以下の条件を満たす必要がある． - 操作後の $ P $ も辞書順で $ Q $ 以下である． - 入れ替える $ 2 $ つの値を $ (x,y) $ とするとき，同じ $ (x,y) $ が今までの操作で入れ替えられたことがない．ここで $ x,y $ の順番は問わない．つまり， $ (x,y) $ を一度入れ替えたあとは $ (x,y) $ でも $ (y,x) $ でも入れ替えることはできない． 最終的な $ P $ としてあり得る順列の中で辞書順最大のものを求めてください． $ 1 $ つの入力につき， $ T $ ケースを解いてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $ $ Q_1 $ $ Q_2 $ $ \ldots $ $ Q_N $

各テストケースについて，答えとなる順列を出力せよ．

### Sample Explanation 1 $ 1 $ つめのテストケースでは，以下のように操作するのが最適です． - $ P=(1,2,3) $ からスタート - $ (2,3) $ を入れ替え， $ P=(1,3,2) $ になる - $ (1,3) $ を入れ替え， $ P=(3,1,2) $ になる $ 2 $ つめのテストケースでは，一度も操作を行わないのが最適です． ### Constraints - $ 1 \leq T \leq 500000 $ - $ 2 \leq N \leq 10^6 $ - $ P $ は $ (1,2,\ldots,N) $ の順列である - $ Q $ は $ (1,2,\ldots,N) $ の順列である - $ P $ は辞書順で $ Q $ 以下である - $ T $ ケースにわたる $ N $ の総和は $ 10^6 $ 以下 - 入力はすべて整数