超级大神 zfr 推荐的题目/se。

首先考虑 $S=2$ 的情况，我们希望每个题目在左右两边被选择的次数之差不超过 $1$，其实是一个经典 trick，我们把每个题目建一个点，进行一个二分图染色，连边就是对于一个评测机测评的两个点相连，题目编号相同的点两两随机连边即可，我们发现这个一定是一个二分图。 ::::info[证明] 考虑反证，考虑记连接编号相同的点的边为红边，连接同一评测机的两点的边为蓝边，那么我们一个奇环一定存在说我连续走两个红边或者两个蓝边，因为一个点最多连一个红边一个蓝边，这样就矛盾了。 :::: 这样我们可以 $O(n)$ 解决 $S=2$ 的情况。

然后考虑分治，你发现 $S=2$ 的信息对于上层合并其实有 0 的作用，你考虑从上层处理的时候就给下层操作出来一个比较有用的性质。

考虑在 $solve(l,r)$ 的时候先给 $[l,mid],[mid+1,r]$ 两个区域进行一些分配，你发现对于一个题目，你令两边的题目数量之差不超过 $1$ 即可，正确性其实不太显然。 ::::info[证明] 考虑对于一个长度为 $2^k$ 的一个区间，一道题目出现 $t$ 次，我们想要证明按照这样分配，每个位置出现次数为 $\lfloor \frac{t}{2^k} \rfloor$ 或者 $\lfloor \frac{t}{2^k} \rfloor+1$，记这样的命题为 $(t,k)$。

考虑对 $k$ 做数学归纳法，$k=1$ 的时候正确性显然。

对于 $k>1$，此时若 $t$ 为偶数，那么左右两边均对应到 $(\frac t 2,k-1)$ 的命题，依旧正确。

若 $t$ 为奇数，那么左边会变成 $(\frac{t+1} 2,k-1)$，右边是 $(\frac{t-1}2,k-1)$，我们发现两个命题不能直接合成当且仅当 $\lfloor\frac{t+1}{2^k}\rfloor \not = \lfloor\frac{t-1}{2^k}\rfloor$，又因为 $t\bmod 2=1$，所以 $t=r2^k-1(r\in \N_+)$，你发现左边的情况就是有 $r2^{k-1}$ 个题目，这个时候每个位置一定会分配 $r$ 个题目，右边会分配 $r-1$ 或 $r$ 个题目，这样依旧是正确的。 :::: 考虑怎么建图，其实和 $S=2$ 差不多，考虑每种编号两两连边，对于一个评测机的题目也两两连边，证明和上面一样，容易证明是二分图。

每次分治跑一遍二分图染色，每个点会被跑 $k$ 遍，时间复杂度 $O(nSk)$。

const int N=1e5+5,M=5e5+5;
int n,s,t;
vector<int> seq[N];
inline int id(int i,int j){return (i-1)*s+j+1;}
vector<int> to[M];
bool vis[M],col[M];
int las[N];
void dfs(int u){
	if(vis[u])return ;
	vis[u]=1;
	for(int v:to[u])col[v]=col[u]^1,dfs(v);
}
inline void add(int a,int b){to[a].pb(b),to[b].pb(a);}
void solve(int l,int r){
	if(l==r)return ;
	int mid=(l+r)>>1;
	for(int i=1;i<=n;i++)for(int j=l;j<=r;j++)to[id(i,j)].clear();
	for(int i=1;i<=n;i++){
		for(int j=l,v=seq[i][j];j<=r;v=seq[i][++j]){
			if(las[v])add(las[v],id(i,j));
			las[v]=las[v]?0:id(i,j);
		}
	}
	for(int i=1;i<=n;i++)for(int j=l;j<=mid;j++){
		add(id(i,j),id(i,j+mid+1-l));
	}
	for(int i=1;i<=n;i++)for(int j=l;j<=r;j++)las[seq[i][j]]=0;
	for(int i=1;i<=n;i++)for(int j=l;j<=r;j++)
		vis[id(i,j)]=col[id(i,j)]=0;
	for(int i=1;i<=n;i++)for(int j=l;j<=r;j++)
		if(!vis[id(i,j)])col[id(i,j)]=0,dfs(id(i,j));
	for(int i=1;i<=n;i++)for(int j=l;j<=mid;j++)
		if(col[id(i,j)])swap(seq[i][j],seq[i][j+mid+1-l]);
	solve(l,mid),solve(mid+1,r);
}
int main(){
	n=read(),s=read(),t=read();
	for(int i=1;i<=n;i++)for(int j=0;j<s;j++)seq[i].pb(read());
	solve(0,s-1);
	for(int i=1;i<=n;i++){
		for(int v:seq[i])printf("%d ",v);
		printf("\n");
	}
}