AT_awtf2026algo_d Adj Swap Lex Max

给定排列 $P$ 和 $Q$，它们都是 $ (1,2,\ldots,N) $ 的一个排列。已知 $P$ 在字典序上不大于 $Q$。 你可以进行如下操作任意次（也可以不做）： - 选择 $P$ 的两个相邻元素并交换。这需要满足以下条件： - 操作后的 $P$ 依然在字典序上不大于 $Q$。 - 设 $(x,y)$ 为被交换的两个值，$(x,y)$ 这对数对在之前的操作中从未被交换过（无论顺序，即一旦交换过 $(x,y)$，则 $(x,y)$ 和 $(y,x)$ 都不能再交换）。 请你求出 $P$ 最终能变成的字典序最大的排列。 一共有 $T$ 组测试数据，请分组输出答案。

输入从标准输入读取，格式如下： > $T$ > $case_1$ > $case_2$ > $\vdots$ > $case_T$ 每组测试数据格式如下： > $N$ > $P_1$ $P_2$ $\ldots$ $P_N$ > $Q_1$ $Q_2$ $\ldots$ $Q_N$

对于每组测试数据，输出所求的排列。

### 样例解释 1 在第一组测试数据中，最优操作如下： - 初始 $P=(1,2,3)$。 - 交换 $(2,3)$，得到 $P=(1,3,2)$。 - 交换 $(1,3)$，得到 $P=(3,1,2)$。 在第二组测试数据中，不进行任何操作是最优的。 ### 数据范围 - $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$。 由 ChatGPT 5 翻译