AT_awtf2026algo_d Adj Swap Lex Max

You are given permutations $ P $ and $ Q $ of $ (1,2,\ldots,N) $ . Here, $ P $ is lexicographically not greater than $ Q $ . You can perform the following operation zero or more times. - Choose two adjacent elements of $ P $ and swap them. Here, the following conditions must be satisfied. - $ P $ after the operation is still lexicographically not greater than $ Q $ . - Let $ (x,y) $ be the two values being swapped. The pair $ (x,y) $ has never been swapped in previous operations. Here, the order of $ x,y $ does not matter. That is, once $ (x,y) $ has been swapped, neither $ (x,y) $ nor $ (y,x) $ can be swapped again. Find the lexicographically greatest permutation that $ P $ can become in the end. Solve $ T $ cases for each input.

The input is given from Standard Input in the following format: > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ Each test case is given in the following format: > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $ $ Q_1 $ $ Q_2 $ $ \ldots $ $ Q_N $

For each test case, output the sought permutation.

### Sample Explanation 1 In the first test case, it is optimal to perform operations as follows. - Start with $ P=(1,2,3) $ . - Swap $ (2,3) $ , resulting in $ P=(1,3,2) $ . - Swap $ (1,3) $ , resulting in $ P=(3,1,2) $ . In the second test case, it is optimal to perform no operations at all. ### Constraints - $ 1 \leq T \leq 500000 $ - $ 2 \leq N \leq 10^6 $ - $ P $ is a permutation of $ (1,2,\ldots,N) $ . - $ Q $ is a permutation of $ (1,2,\ldots,N) $ . - $ P $ is lexicographically not greater than $ Q $ . - The sum of $ N $ over the $ T $ cases is at most $ 10^6 $ . - All input values are integers.