题目描述

一栋 $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 的限制。

对于第一组数据的第一组询问，不需要操作。

对于第一组数据的第二组询问：

【样例解释 #2】

该样例满足子任务 7 的限制。

【数据范围】

本题采用捆绑测试。

对于所有数据，$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$。