一道有意思的题，感谢 jason_sun 为解法提供的思路。

首先对于第一个子任务，我们可以直接打表。

对于第二个子任务，我们发现每次询问至少有 $m$ 个连续的后缀是空的，那么我们考虑先在这些空的位置上将电梯按照相对顺序排列好。那么我们在 $0$ 直接从右往左扫一遍进行操作，后面等他们到位后在移动过来即可，这样第一遍扫和移动均要 $m$ 次操作，然后每次移动的最远距离是 $n$，所以最多会等待 $2n$ 的时间，满足要求。

对于后面的子任务，我们考虑将电梯分类，分成左移点（即 $a_i< i$）和右移点（即 $a_i\geq i$）。

假设我们先不考虑存在只需要向左移动一步的点（下面称为关键点），那么我们可以进行如下操作：

1. 在 $0$ 时刻从左往右扫，让左移点直接移动到其目的地，让右移点向左移动一步。可以证明当扫到第 $i$ 个点时其左侧的所有点都在运动。（一共需要花费 $m$ 步）。
2. 让时间流逝 $1$。（花费 $1$ 步）。
3. 从右向左扫，让所有右移点移动到目的地，因为没有关键点，所以可以证明不会产生冲突。（最多花费 $m$ 步）。
4. 等待所有点到达目的地。（最多花费 $n$ 步）。

那现在的问题在于如何消除关键点了。

首先我们可以发现在哪层没有电梯是不会影响上述操作的，那么我们先让其移动到最左侧，在移动过程中进行处理。

现在每个点都向右移动了一步，那么就是说如果 $a_i=i$ 就说明在最后他是一共关键点。我们对序列相邻的两个数进行分组，如果 $m$ 是奇数那么最后一组有三个元素（要特殊讨论）。

如果在一组中存在关键点，那么我们交换这两个点即可。就是说对于一组 $i,i+1,i+2$，其中 $i,i+1$ 是一组，$i+2$ 是空楼层，那么我们进行这样操作 $i+2,i+2,0,i+1$，手动模拟一下发现这个时候两台电梯还在运行中，那为什么不让他们移动到终点呢？因为我们要保证对一组操作时前一组不会影响电梯的选择，就要使前一组在运行中。

这样我们从右向左扫一遍挨个处理即可。

现在讨论一下最后三个元素的情况，因为三个元素的排列顺序只有 $6$ 中，那么我们直接打表这六种情况，因为要消除关键点所以每种情况有 $3$ 个限制，判断并选择适合的情况即可（同时要保证进行下一组之前要都在运行）。

现在我们来分析一下处理所需要花费的步数：

通过打表我们知道三个元素交换最多需要 $7$ 步，然后对于前面最多 $\frac m2$ 组中，最坏情况下需要 $2m$ 次操作，那么这里需要的总操作次数最多是 $2m+2$ 步。之所以 $+2$ 是因为后面三个数要 $+1$，而且最后第一组完成后要等待时间移动 $1$ 来让所有电梯归位。

那么最后的总步数是 $2m+2+m+1+n+m=5n-1$，可以满足条件。

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll long long
#define mk make_pair
#define reaD read
#define raed read
#define haed head
#define cotu cout
#define se second
#define fi first
#define itn int
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
bool Mst;
const int Max=2e5+10;
const int mod=998244353;
const int inf=1e9+10;

inline int read(){
	int res=0,v=1;
	char c=getchar();
	while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
	while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
	return res*v;
}

int n,m,a[Max],o,b[Max];
int num=0;
void work(int opt=0){
	int now=n;
	if(m&1){//分讨 
		if(a[now-1]!=now-1&&a[now-2]!=now-2&&a[now-3]!=now-3){  
			//1 2 3
			if(!opt)num+=3;
			else cout << now << ' '<< now-1 << ' ' << now-2 << ' ';
			a[now]=a[now-1];a[now-1]=a[now-2];a[now-2]=a[now-3];a[now-3]=0;
		}else if(a[now-3]!=now-3&&a[now-1]!=now-2&&a[now-2]!=now-1){
			//1 3 2
			if(!opt)num+=5;
			else cout << now << ' ' << now << ' ' << "0 " << now-1 << ' ' << now-2 << ' ';
			a[now]=a[now-2];a[now-1]=a[now-1];a[now-2]=a[now-3];a[now-3]=0;
		}else if(a[now-2]!=now-3&&a[now-3]!=now-2&&a[now-1]!=now-1){
			//2 1 3
			if(!opt)num+=5;
			else cout << now << ' ' << now-1 << ' ' << now-1 << ' ' << "0 " << now-2 << ' ';
			a[now]=a[now-1];a[now-1]=a[now-3];a[now-2]=a[now-2];a[now-3]=0;
 		}else if(a[now-2]!=now-3&&a[now-1]!=now-2&&a[now-3]!=now-1){
 			//2 3 1
 			if(!opt)num+=7;
 			else cout << now << ' ' << now-1 << ' ' << now << ' ' << "0 0 " << now-2 << ' ' << now-1<< ' ';
			a[now]=a[now-3];a[now-1]=a[now-1];a[now-2]=a[now-2];a[now-3]=0;
		}else if(a[now-1]!=now-3&&a[now-3]!=now-2&&a[now-2]!=now-1){
			//3 1 2
			if(!opt)num+=6;
			else cout << now << ' ' << now << ' ' << now-1 << " 0 " << now-2 << ' ';
			int z=a[now-1];a[now]=a[now-2];a[now-1]=a[now-3];a[now-2]=z;a[now-3]=0;
		}else {
			//3 2 1
			if(!opt)num+=7;
			else cout << now << ' ' << now << ' ' << now << " 0 " << now-2 << " 0 " << ' ' << now-1 << ' ';
			int z=a[now-1];a[now]=a[now-3];a[now-1]=a[now-2];a[now-2]=z;a[now-3]=0;
		}
		now-=3; 
	}
	for(;now>1;now-=2){
		if(a[now-1]==now-1||a[now-2]==now-2){
			if(opt){//交换 
				cout << now << ' ' << now << " 0 "<< now-1 << ' ';
			}else{
				num+=4;
			}
			a[now]=a[now-2];a[now-2]=0;
		}else{
			if(opt){
				cout << now << ' ' << now-1 << ' ';
			}else num+=2;
			a[now]=a[now-1];a[now-1]=a[now-2];a[now-2]=0;
		}
	}
	if(opt)cout << "0 ";else num++;
	int val=0;
	for(int i=2;i<=n;++i){
		if(a[i]<i){
			val=max(i-a[i]-1,val);
			if(opt)cout << a[i] << ' ';
			else ++num;
		}else{
			if(opt)cout << i-1 << ' ';
			else ++num;
		}
	}
	if(opt)cout << "0 ";else num++;
	for(int i=n;i>=2;--i){
		if(a[i]>=i){
			val=max(val,a[i]-i+1);
			if(opt)cout << a[i] << ' ';
			else ++num;
		}
	}
	num+=val;
	if(opt){
		for(int i=1;i<=val;++i)cout << "0 ";
	}
} 

namespace Sub1{
	
	
	void main(){
		if(a[1]==1){
			cout << "0\n\n";
		}else{
			cout << "7\n3 3 0 1 0 2 0\n";
		}
	}
	
}

namespace Sub2{
	int res=0;
	int ys[Max];
	void main(){
		cout << 2*(n+m) << "\n";
		for(int i=m;i>=1;--i){
			cout << a[i]+m << ' ';
		}
		for(int i=1;i<=n;++i)cout << "0 ";
		for(int i=1;i<=m;++i)cout << i << ' ';
		for(int i=1;i<=n;++i)cout << "0 ";
		cout << '\n';
	}
}


bool Med;
signed main(){
	int T=read();
	while(T--){
		int q=read();n=read();m=read();o=read();
		while(q--){
			for(int i=1;i<=m;++i)b[i]=a[i]=read();
			if(m==2){
				Sub1::main();
				continue;
			}
			if(m==n/2){
				Sub2::main();
				continue;
			}
			num=0;work();
			cout << num << "\n";
			for(int i=1;i<=m;++i)a[i]=b[i];
			work(1);
		}
	}

	cerr<< "Time: "<<clock()/1000.0 << "s\n";
	cerr<< "Memory: " << (&Mst-&Med)/1000000.0 << "MB\n";
	return 0;
}
/*

*/