循环位移

Problem Description

算法竞赛彻底怒了，算法竞赛指出了最核心的矛盾点：如果 EG 真的训完了几年的算法竞赛，怎么可能连排序都不会。 这确实是 EG 的严重失误，他需要彻底承认自己完全没有水平，每天的生活就是无限的摆烂，过的题也全是签到、变着花样耍阴招的垃圾水题。 现在毫无天赋的 EG 要想办法把这道题糊弄过去，于是他找到了你。 EG 有一个长度为 $n$ 的排列 $a$，但是这个排列被神秘人打乱了，因此 EG 的排列是一个随机排列。作为他的好朋友，你需要帮助他，将这个排列排序为 $1 \sim n$ 的升序排列。 在操作开始前，你可以指定一个正整数 $x(2 \leq x \leq n)$。由于你的能力有限，$x$ 不能超过 $1.9 \times 10^3$。 你可以进行不超过 $1.9 \times 10^6$ 次操作，每次操作你都可以选择一个长度为 $x$ 的子区间，并将该区间向左循环位移一位。具体地，设所选区间为 $[l, l + x - 1]$，则区间 $[l + 1, l + x - 1]$ 中的数字都会同时向左移动一位，同时原先在 $l$ 位置上的数会移动到 $l + x - 1$ 处。

Input

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T(1 \leq T \leq 3)$，表示数据组数。对于每组测试数据： 第一行一个正整数 $n(2 \leq n \leq 1.9 \times 10^4)$，表示排列 $a$ 的长度。 第二行 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，表示排列 $a$。保证排列 $a$ 随机。

Output

对于每组测试数据： 第一行一个正整数 $x(2 \leq x \leq \min(n, 1.9 \times 10^3))$，表示你指定的操作参数。

第二行一个整数 $m(0 \leq m \leq 1.9 \times 10^6)$，表示操作次数。

第三行 $m$ 个正整数 $l_1, l_2, \cdots, l_m$，其中第 $i$ 个数 $l_i$ 表示第 $i$ 次操作区间 $[l_i, l_i + x - 1]$ 的左端点。

Sample Input

1
6
6 1 3 5 2 4

Sample Output

3
7
3 1 3 2 3 4 3

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（2）