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

Мы называем массив $$$[b_1, b_2, \dots, b_m]$$$ длины $$$m$$$ палиндромным, если выполняется следующее условие:

  • $$$b_i = b_{m-i+1}$$$ для всех $$$1 \le i \le m$$$

Другими словами, массив является палиндромным, если он читается одинаково вперед и назад.

Вам дан массив $$$[a_1, a_2, \dots , a_n]$$$ из $$$n$$$ целых чисел, где $$$1 \le a_i \le n$$$, и целое число $$$k$$$.

Вам необходимо выполнить следующую операцию ровно $$$k$$$ раз:

  • выбрать целое число $$$x$$$, такое что $$$1 \le x \le n$$$,
  • добавить $$$x$$$ в конец массива $$$a$$$.

Ваша цель — выполнить эти $$$k$$$ операций таким образом, чтобы количество палиндромных подмассивов$$$^{\text{∗}}$$$ в получившемся массиве было минимальным.

Выведите $$$k$$$ целых чисел, которые вы выбрали для каждой операции, в порядке их добавления.

$$$^{\text{∗}}$$$Массив $$$b$$$ является подмассивом массива $$$a$$$, если $$$b$$$ может быть получен из $$$a$$$ путем удаления нескольких (возможно, нуля или всех) элементов с начала и нескольких (возможно, нуля или всех) элементов с конца. В частности, массив является подмассивом самого себя.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$3 \le n \le 2\cdot10^5, 1 \le k \le n$$$) — длина массива $$$a$$$.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots , a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot10^5$$$.

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

Для каждого набора входных данных выведите $$$k$$$ целых чисел, выбранных для операций добавления, в порядке их добавления, так, чтобы общее количество палиндромных подмассивов в получившемся массиве было минимальным.

Если есть несколько ответов, вы можете вывести любой из них.

Пример
Входные данные
5
4 1
1 3 3 4
4 2
2 2 2 2
5 1
4 1 5 2 2
6 3
1 2 3 4 5 6
5 3
3 2 5 2 3
Выходные данные
2 
1 3 
3 
3 4 1
4 1 5
Примечание

Для первого примера, если мы добавим $$$2$$$ в конец массива, $$$a$$$ станет $$$[1, 3, 3, 4, 2]$$$. Теперь в $$$a$$$ всего $$$6$$$ палиндромных подмассивов — $$$[1]$$$, $$$[3]$$$, $$$[3]$$$, $$$[4]$$$, $$$[2]$$$, $$$[3, 3]$$$.