给你一个长度为 $$$n$$$ 的排列$$$^{\text{∗}}$$$ $$$p$$$。还有两个传送门位于位置 $$$x$$$ 和 $$$y$$$ ($$$x \lt y$$$)。
位置 $$$i$$$ 处的入口最初位于数组的第 $$$i$$$ 和第 $$$(i+1)$$$ 元素之间。具体来说,如果$$$i=0$$$,则门户位于数组的第一个元素之前,如果$$$i=n$$$,则门户位于最后一个元素之后。
您可以执行以下两种操作之一 多次 如你所愿:
- 删除一个入口左侧的元素并将其插入另一个入口右侧。
- 删除一个入口右侧的元素并将其插入另一个入口左侧。
让 $$$\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{†}}$$$如果存在索引 $$$i$$$,则对于所有索引 $$$1 \leq j \lt i$$$ 和 $$$a_i \lt b_i$$$,$$$a_j = b_j$$$ 按字典顺序排列 $$$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 \lt y \leq n$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ — 长度 $$$n$$$ 的排列。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一行包含 $$$n$$$ 整数 - 您可以获得的按字典顺序排列的最小排列。
示例
输入复制
44 0 43 1 4 23 1 23 2 15 1 31 3 5 2 42 0 11 2
输出复制
1 4 2 32 3 11 2 3 5 41 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]$$$,这是可以获得的按字典顺序排列的最小可能排列。
在第四个测试用例中,最好不进行任何操作。