D. Портал
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$. Также есть два портала, расположенные на позициях $$$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$$$, такой что $$$a_j = b_j$$$ для всех индексов $$$1 \leq j \lt i$$$ и $$$a_i \lt b_i$$$.

Входные данные

Первая строка содержит целое число $$$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$$$ целыми числами — лексикографически наименьшую перестановку, которую вы можете получить.

Пример
Входные данные
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 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]$$$, что является лексикографически наименьшей возможной перестановкой, которую можно получить.

В четвертом наборе входных данных оптимально не выполнять никаких операций.