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.

给你两个 $(1,2,\ldots,N)$ 的排列 $P$ 和 $Q$，其中 $P$ 在字典序上不大于 $Q$。

你可以执行以下操作零次或多次：

• 选择 $P$ 中两个相邻的元素并交换它们。该操作需满足以下条件：
  • 操作后的 $P$ 在字典序上仍不大于 $Q$；
  • 设被交换的两个值为 $(x,y)$，则该数对 $(x,y)$ 在之前的所有操作中均未被交换过（注意：$(x,y)$ 与 $(y,x)$ 被视为同一数对；即一旦 $(x,y)$ 被交换过，则今后既不允许交换 $(x,y)$，也不允许交换 $(y,x)$）。

求 $P$ 最终所能变成的字典序最大的排列。

对每组输入，求解 $T$ 个测试用例。

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$

输入从标准输入中按以下格式给出：

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

每个测试用例按以下格式给出：

$N$
$P_1$ $P_2$ $\ldots$ $P_N$
$Q_1$ $Q_2$ $\ldots$ $Q_N$

For each test case, output the sought permutation.

对于每个测试用例，输出所求的排列。

Sample 1 Explanation:
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.

样例 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$。
• 所有输入值均为整数。