CF2162E.Beautiful Palindromes

We call an array $[b_1, b_2, \dots, b_m]$ of length $m$ palindromic if the following condition holds:

• $b_i = b_{m-i+1}$ for all $1 \le i \le m$

In other words, an array is palindromic if it reads the same forward and backward.

You are given an array $[a_1, a_2, \dots , a_n]$ of $n$ integers where $1 \le a_i \le n$ and an integer $k$.

You are required to perform the following operation exactly $k$ times:

• choose an integer $x$ such that $1 \le x \le n$,
• append $x$ to the end of the array $a$.

Your goal is to perform these $k$ operations in such a way that the number of palindromic subarrays$^{\text{∗}}$ in the resulting array is minimized.

Output the $k$ integers you chose for each operation, in the order they were appended.

$^{\text{∗}}$An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

我们称一个长度为 $m$ 的数组 $[b_1, b_2, \dots, b_m]$ 是回文的，如果满足以下条件：

• 对所有 $1 \le i \le m$，有 $b_i = b_{m-i+1}$。

换言之，一个数组是回文的，当且仅当它正读与反读完全相同。

给定一个由 $n$ 个整数组成的数组 $[a_1, a_2, \dots , a_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$ 的一个子数组。特别地，一个数组是其自身的子数组。

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($3 \le n \le 2\cdot10^5, 1 \le k \le n$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots , a_n$ ($1 \le a_i \le n$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all the test cases does not exceed $2\cdot10^5$.

输入的第一行包含一个整数 $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$。

For each test case, print the $k$ integers chosen for the append operations, in the order they were appended, such that the total number of palindromic subarrays in the resulting array is minimized.

If there are multiple answers, you may output any one of them.

对于每个测试用例，请按追加操作执行的顺序输出所选择的 $k$ 个整数，使得最终数组中回文子数组的总数最小。

若存在多个满足条件的答案，输出任意一个即可。

For the first test case, if we append $2$ to the end of the array, $a$ becomes $[1, 3, 3, 4, 2]$. Now $a$ has only $6$ palindromic subarrays — $[1]$, $[3]$, $[3]$, $[4]$, $[2]$, $[3, 3]$.

对于第一个测试用例，如果我们在数组末尾追加 $2$，则 $a$ 变为 $[1, 3, 3, 4, 2]$。此时 $a$ 仅有 $6$ 个回文子数组——$[1]$、$[3]$、$[3]$、$[4]$、$[2]$、$[3, 3]$。