题目描述

一栋 $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$			运动
$4$		运动
$0$	$1$		$3$
	$2$
$1$			运动
$0$	$3$	$4$
$2$		运动
$0$	$4$		$1$
	$5$	$2$

【样例解释 #2】

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

【数据范围】

本题采用捆绑测试。

子任务	$n \le$	$m =$	$o =$	分值
1	$3$	$2$	$7$
2	$100$	$\lfloor \frac{n}{2} \rfloor$	$2\times(m+n)$	$11$
3	$40$	$n-1$	$3 \times n^3$	$17$
4	$200$		$5 \times n^2$	$19$
5	$4000$		$50 \times n$	$17$
6	$5 \times 10^{4}$		$6 \times n$	$16$
7			$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$。