CF2200D.Portal

You are given a permutation$^{\text{∗}}$ $p$ of length $n$. There are also two portals located at positions $x$ and $y$ ($x \lt y$).

A portal at position $i$ is initially located between the $i$-th and $(i+1)$-th elements of the array. Specifically, if $i=0$, then the portal is located before the first element of the array, and if $i=n$, then the portal is located after the last element.

You may perform either of the following two operations as many times as you like:

1. Remove the element to the immediate left of one portal and insert it to the immediate right of the other portal.
2. Remove the element to the immediate right of one portal and insert it to the immediate left of the other portal.

Let $\mathbf{\color{red}{\mathcal{O}}}$ denote a portal. For example, if $p$ is $[3,\mathbf{\color{red}{\mathcal{O}}},2,4,\mathbf{\color{red}{\mathcal{O}}},1]$:

• Using operation $1$ on the left and right portals respectively results in the arrays $[\mathbf{\color{red}{\mathcal{O}}},2,4,\mathbf{\color{red}{\mathcal{O}}},3,1]$ and $[3,\mathbf{\color{red}{\mathcal{O}}},4,2,\mathbf{\color{red}{\mathcal{O}}},1]$.
• Using operation $2$ on the left and right portals respectively results in the arrays $[3,\mathbf{\color{red}{\mathcal{O}}},4,2,\mathbf{\color{red}{\mathcal{O}}},1]$ and $[3,1,\mathbf{\color{red}{\mathcal{O}}},2,4,\mathbf{\color{red}{\mathcal{O}}}]$.

Find the lexicographically$^{\text{†}}$ smallest permutation you can obtain using these operations. Note that portals do not affect the lexicographical comparison of permutations.

$^{\text{∗}}$A permutation of length $n$ is an array of length $n$ containing each integer from $1$ to $n$ exactly once.

$^{\text{†}}$A permutation $a$ is lexicographically smaller than permutation $b$ if there exists an index $i$ such that $a_j = b_j$ for all indices $1 \leq j \lt i$ and $a_i \lt b_i$.

给你一个长度为 $n$ 的排列$^{\text{∗}}$ $p$。此外，还有两个传送门分别位于位置 $x$ 和 $y$（其中 $x \lt y$）。

位于位置 $i$ 的传送门初始时处于数组第 $i$ 个元素与第 $(i+1)$ 个元素之间。具体而言：若 $i = 0$，则传送门位于数组第一个元素之前；若 $i = n$，则传送门位于数组最后一个元素之后。

你可以任意次执行以下两种操作之一：

1. 将某一个传送门正左侧的元素移除，并将其插入到另一个传送门的正右侧；
2. 将某一个传送门正右侧的元素移除，并将其插入到另一个传送门的正左侧。

用 $\mathbf{\color{red}{\mathcal{O}}}$ 表示一个传送门。例如，若 $p$ 为 $[3,\mathbf{\color{red}{\mathcal{O}}},2,4,\mathbf{\color{red}{\mathcal{O}}},1]$：

• 对左、右传送门分别执行操作 $1$，得到的数组分别为 $[\mathbf{\color{red}{\mathcal{O}}},2,4,\mathbf{\color{red}{\mathcal{O}}},3,1]$ 和 $[3,\mathbf{\color{red}{\mathcal{O}}},4,2,\mathbf{\color{red}{\mathcal{O}}},1]$；
• 对左、右传送门分别执行操作 $2$，得到的数组分别为 $[3,\mathbf{\color{red}{\mathcal{O}}},4,2,\mathbf{\color{red}{\mathcal{O}}},1]$ 和 $[3,1,\mathbf{\color{red}{\mathcal{O}}},2,4,\mathbf{\color{red}{\mathcal{O}}}]$。

求使用这些操作所能得到的字典序$^{\text{†}}$最小的排列。注意：传送门不参与排列的字典序比较。

$^{\text{∗}}$ 长度为 $n$ 的排列是指一个长度为 $n$ 的数组，其中恰好包含 $1$ 到 $n$ 的每个整数各一次。

$^{\text{†}}$ 排列 $a$ 字典序小于排列 $b$，当且仅当存在某个下标 $i$，使得对所有满足 $1 \leq j \lt i$ 的下标 $j$ 均有 $a_j = b_j$，且 $a_i \lt b_i$。

The first line contains an integer $t$ ($1 \leq t \leq 2\cdot 10^4$) — the number of test cases.

For each test case, the first line contains three integers $n$, $x$, and $y$ ($1 \leq n \leq 2 \cdot 10^5$, $0 \leq x \lt y \leq n$).

The second line of each test case contains $n$ integers $p_1, p_2, \dots, p_n$ — a permutation of length $n$.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 2\cdot 10^4$）—— 测试用例的数量。

对于每个测试用例，第一行包含三个整数 $n$、$x$ 和 $y$（$1 \leq n \leq 2 \cdot 10^5$，$0 \leq x \lt y \leq n$）。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ —— 一个长度为 $n$ 的排列。

所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output a line with $n$ integers — the lexicographically smallest permutation you can obtain.

对于每个测试用例，输出一行包含 $n$ 个整数——你能得到的字典序最小的排列。

Let $\mathbf{\color{red}{\mathcal{O}}}$ denote a portal.

In the first test case, the array is $[\mathbf{\color{red}{\mathcal{O}}},3,1,4,2,\mathbf{\color{red}{\mathcal{O}}}]$. Using operation $2$ on the left portal results in $[\mathbf{\color{red}{\mathcal{O}}},1,4,2,3,\mathbf{\color{red}{\mathcal{O}}}]$, which is the lexicographically smallest possible permutation that can be obtained.

The operation described above.

In the second test case, the array is $[3,\mathbf{\color{red}{\mathcal{O}}},2,\mathbf{\color{red}{\mathcal{O}}},1]$. Using operation $1$ on the left portal results in $[\mathbf{\color{red}{\mathcal{O}}},2,\mathbf{\color{red}{\mathcal{O}}},3,1]$, which is the lexicographically smallest possible permutation that can be obtained.

In the fourth test case, it is optimal not to do any operations.

设 $\mathbf{\color{red}{\mathcal{O}}}$ 表示一个传送门。

在第一个测试用例中，数组为 $[\mathbf{\color{red}{\mathcal{O}}},3,1,4,2,\mathbf{\color{red}{\mathcal{O}}}]$。对左侧的传送门执行操作 $2$，得到 $[\mathbf{\color{red}{\mathcal{O}}},1,4,2,3,\mathbf{\color{red}{\mathcal{O}}}]$，这是所能获得的字典序最小的排列。

上述所描述的操作。

在第二个测试用例中，数组为 $[3,\mathbf{\color{red}{\mathcal{O}}},2,\mathbf{\color{red}{\mathcal{O}}},1]$。对左侧的传送门执行操作 $1$，得到 $[\mathbf{\color{red}{\mathcal{O}}},2,\mathbf{\color{red}{\mathcal{O}}},3,1]$，这是所能获得的字典序最小的排列。

在第四个测试用例中，最优策略是不执行任何操作。