← 返回题目列表

Codeforces · 2162/E

E. 美丽的回文

中文机器翻译题面 查看原题

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

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

换句话说,如果向前和向后读取相同的数组,则该数组是回文数组。

给定一个由 $$$n$$$ 整数组成的数组 $$$[a_1, a_2, \dots , a_n]$$$,其中 $$$1 \le a_i \le n$$$ 和一个整数 $$$k$$$。

您需要执行以下操作 正是 $$$k$$$ 次:

  • 选择一个整数 $$$x$$$ 使得 $$$1 \le x \le n$$$,
  • 将 $$$x$$$ 附加到数组 $$$a$$$ 的末尾。

您的目标是以最小化结果数组中回文子数组 $$$^{\text{*}}$$$ 的数量的方式执行这些 $$$k$$$ 操作。

按照附加顺序输出您为每个操作选择的 $$$k$$$ 整数。

$$$^{\text{*}}$$$数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过从 $$$a$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来从 $$$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]$$$。