【MX-X4-T6】「Jason-1」电梯

一栋 $n$ 层的楼有 $m$ 部电梯，每部电梯有静止与运动两种状态。 初始时，第 $i$ 部电梯静止于第 $i$ 层。给定一个 $1 \sim m$ 的排列 $p$，你希望最终第 $i$ 部电梯位于 $p_i$ 层。 你可以进行以下两种操作： - `0`：让时间向后运动一个时刻。 - `x`：其中 $x$ 为不超过 $n$ 的正整数。 - 执行该操作时，需要满足：$x$ 层不存在静止的电梯；距离 $x$ 层距离最近的$^\dagger$ 静止的电梯存在且唯一。 - 令 $y$ 为最近的静止的电梯编号，$z$ 为其位置。则电梯 $y$ **立刻**变为运动的电梯，并在 $\lvert x - z\rvert$ 时刻后的**所有操作前**到达楼层 $x$ 并变为静止的电梯。 $^\dagger$：位于 $a$ 层的一部电梯与楼层 $x$ 的距离为 $\lvert a - x\rvert$。 **注意：你需要保证，任何时刻不存在两个静止的电梯位于同一楼层。** 对于每组数据，有一个评分参数 $o$，你需要构造出总操作次数不超过 $o$ 的方案才能通过该组数据。 本题使用**自定义校验器**检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出**任意一种**。

**本题输入包含多组数据。** 第一行，一个正整数 $T$，表示数据组数。对于每组数据： - 第一行，四个正整数 $Q, n, m, o$，分别表示询问组数、楼层数、电梯数、与评分参数。 - 接下来 $Q$ 行，每行 $m$ 个整数 $p_1, \ldots, p_m$，表示电梯的目标位置。

对于每组数据： - 共 $2 Q$ 行。对于每个询问，输出两行： - 第一行，一个非负整数 $k$，表示你的方案的操作步数； - 第二行，$k$ 个 $[0, n]$ 中的整数，表示你的具体操作方案。 本题使用**自定义校验器**检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出**任意一种**。

2
2 4 2 12
1 2
2 1
1 10 5 30
5 4 3 2 1

0

9
3 4 0 0 1 0 2 0 0
16
6 6 6 6 6 0 1 0 2 0 3 0 4 0 5 0

1
1 6 5 30
5 4 3 2 1

16
6 6 6 6 6 0 1 0 2 0 3 0 4 0 5 0

**【样例解释 #1】** 该样例满足子任务 2 的限制。 对于第一组数据的第一组询问，不需要操作。 对于第一组数据的第二组询问： | 操作 | 时刻 | 电梯 $1$ 位置 | 电梯 $2$ 位置 | | :----------: | :----------: | :----------: | :----------: | | 初始状态 | $0$ | $1$ | $2$ | | $3$ | $0$ | $1$ | 运动 | | $4$ | $0$ | 运动 | 运动 | | $0$ | $1$ | 运动 | $3$ | | $0$ | $2$ | 运动 | $3$ | | $1$ | $2$ | 运动 | 运动 | | $0$ | $3$ | $4$ | 运动 | | $2$ | $3$ | 运动 | 运动 | | $0$ | $4$ | 运动 | $1$ | | $0$ | $5$ | $2$ | $1$ | **【样例解释 #2】** 该样例满足子任务 7 的限制。 **【数据范围】** **本题采用捆绑测试。** | 子任务 | $n \le$ | $m =$ | $o = $ | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $3$ | $2$ | $7$ | $7$ | | 2 | $100$ | $\lfloor \frac{n}{2} \rfloor$ | $2\times(m+n)$ | $11$ | | 3 | $40$ | $n-1$ | $3 \times n^3$ | $17$ | | 4 | $200$ | $n-1$ | $5 \times n^2$ | $19$ | | 5 | $4000$ | $n-1$ | $50 \times n$ | $17$ | | 6 | $5 \times 10^{4}$ | $n-1$ | $6 \times n$ | $16$ | | 7 | $5 \times 10^{4}$ | $n-1$ | $5 \times n$ | $13$ | 对于所有数据，$1 \le T \le 20$，$2 \le m < n \le 5 \times 10^{4}$，保证 $n, m, o$ 同时满足上述某个子任务的限制，$p$ 为 $1 \sim m$ 的排列，$1 \le Q \le 2\times 10^6$，$\sum o Q \le 2 \times 10^6$。