长度 $$$n$$$ 的恒等排列是一个数组 $$$[1, 2, 3, \dots, n]$$$。
我们对长度 $$$n$$$ 的恒等排列执行了以下操作:
- 首先,我们将其循环向右移动 $$$k$$$ 个位置,其中 $$$k$$$ 对你来说是未知的(你唯一知道的是 $$$0 \le k \le n - 1$$$)。当数组循环右移 $$$k$$$ 个位置时,生成的数组是通过获取原始数组的最后一个元素 $$$k$$$ (不改变它们的相对顺序),然后将 $$$n - k$$$ 第一个元素附加到它们的右侧(也不改变第一个 $$$n - k$$$ 元素的相对顺序)来形成的。例如,如果我们将长度 $$$6$$$ 的恒等排列循环移位 $$$2$$$ 个位置,我们将得到数组 $$$[5, 6, 1, 2, 3, 4]$$$;
- 其次,我们最多执行 $$$m$$$ 次以下操作:选取数组中的任意两个元素并交换它们。
将为您提供 $$$n$$$ 和 $$$m$$$ 的值以及结果数组。您的任务是在循环移位运算中找到 $$$k$$$ 的所有可能值。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。
每个测试用例由两行组成。第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n \le 3 \cdot 10^5$$$; $$$0 \le m \le \frac{n}{3}$$$)。
第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, 从 $$$1$$$ 到 $$$n$$$ 的每个整数在此序列中只出现一次) — 结果数组。
所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,按以下方式打印答案:
- 首先,打印一个整数 $$$r$$$ ($$$0 \le r \le n$$$) — 循环移位操作的 $$$k$$$ 可能值的数量;
- 其次,打印 $$$r$$$ 整数 $$$k_1, k_2, \dots, k_r$$$ ($$$0 \le k_i \le n - 1$$$) — 按升序排列 $$$k$$$ 的所有可能值。
示例
输入 #1
4 4 1 2 3 1 4 3 1 1 2 3 3 1 3 2 1 6 0 1 2 3 4 6 5
输出 #1
1 3 1 0 3 0 1 2 0
注意
考虑这个例子:
- 在第一个测试用例中,循环移位的唯一可能值是 $$$3$$$。如果我们将 $$$[1, 2, 3, 4]$$$ 移动 $$$3$$$ 位置,我们会得到 $$$[2, 3, 4, 1]$$$。然后我们可以交换 $$$3$$$-rd 和 $$$4$$$-th 元素,得到数组 $$$[2, 3, 1, 4]$$$;
- 在第二个测试用例中,循环移位的唯一可能值是 $$$0$$$。如果我们将 $$$[1, 2, 3]$$$ 移动 $$$0$$$ 位置,我们会得到 $$$[1, 2, 3]$$$。然后我们根本不更改数组(我们声明最多进行 $$$1$$$ 交换),因此结果数组保持 $$$[1, 2, 3]$$$;
- 在第三个测试用例中,从 $$$0$$$ 到 $$$2$$$ 的所有值都可以用于循环移位:如果我们将 $$$[1, 2, 3]$$$ 移动 $$$0$$$ 位置,我们得到 $$$[1, 2, 3]$$$。然后我们可以交换 $$$1$$$-st 和 $$$3$$$-rd 元素得到 $$$[3, 2, 1]$$$; 如果我们将 $$$[1, 2, 3]$$$ 移动 $$$1$$$ 位置,我们会得到 $$$[3, 1, 2]$$$。然后我们可以交换 $$$2$$$-nd 和 $$$3$$$-rd 元素得到 $$$[3, 2, 1]$$$; 如果我们将 $$$[1, 2, 3]$$$ 移动 $$$2$$$ 位置,我们会得到 $$$[2, 3, 1]$$$。然后我们可以交换 $$$1$$$-st 和 $$$2$$$-nd 元素得到 $$$[3, 2, 1]$$$;
- 在第四个测试用例中,我们声明在循环移位后没有进行任何交换,但是循环移位的任何值都不能产生数组 $$$[1, 2, 3, 4, 6, 5]$$$。