我们称长度为 $$$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$$$ 整数,以使结果数组中回文子数组的总数最小化。
如果有多个答案,则可以输出其中任何一个。
示例
输入复制
54 11 3 3 44 22 2 2 25 14 1 5 2 26 31 2 3 4 5 65 33 2 5 2 3
输出复制
21 333 4 14 1 5
注意
对于第一个测试用例,如果我们将 $$$2$$$ 追加到数组末尾,则 $$$a$$$ 变为 $$$[1, 3, 3, 4, 2]$$$。现在 $$$a$$$ 只有 $$$6$$$ 回文子数组 - $$$[1]$$$、$$$[3]$$$、$$$[3]$$$、$$$[4]$$$、$$$[2]$$$、$$$[3, 3]$$$。