题目描述

给定一个长度为 $n$ 的排列 $p$。有两个传送门分别位于位置 $x$ 和 $y$（$x < 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}}}]$。

求使用这些操作可以得到的字典序最小的排列。注意，传送门不影响排列的字典序比较。

$^{*}$ 长度为 $n$ 的排列是一个包含 $1$ 到 $n$ 每个整数恰好一次的数组。

$^{+}$ 如果存在一个索引 $i$，使得对于所有 $1 \leq j < i$ 有 $a_j = b_j$，且 $a_i < b_i$，则排列 $a$ 的字典序小于排列 $b$。

输入格式

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

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

4
4 0 4
3 1 4 2
3 1 2
3 2 1
5 1 3
1 3 5 2 4
2 0 1
1 2

输出 #1

1 4 2 3
2 3 1
1 2 3 5 4
1 2

说明/提示

用 $\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]$，这是可以得到的最小的字典序排列。

在第四个测试用例中，最优方案是不进行任何操作。