题目描述

我们称一个长度为 $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$ 的末尾。

你的目标是，使得最终得到的新数组中回文子数组 $^{\ast}$ 的总数最少。

请输出每次操作中你选择添加的 $k$ 个整数，按照添加顺序给出。

$^{\ast}$ 若数组 $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]$。

由 ChatGPT 5 翻译

来源

Codeforces 2162E，英文题名 Beautiful Palindromes。