#include<bits/stdc++.h>
#define reg register
int fa[4010];
int find(reg int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void merge(reg int x,reg int y){x=find(x),y=find(y); fa[x]=y;}
bool reversal(int N, int M, std::vector<std::string> P){
	for (reg int x=0;x<M;x++) for (reg int y=0;y<M;y++){
		reg int n=N/M+(N%M>x),m=N/M+(N%M>y);
		for (reg int i=0;i<n+m<<1;i++) fa[i]=i;
		for (reg int i=0;i<n;i++) for (reg int j=0;j<m;j++){
			reg int px=x+i*M,py=y+j*M;
			if (P[px][py]=='X') merge(i,j+n),merge(i+n+m,j+n+n+m);
			else merge(i+n+m,j+n),merge(i,j+n+n+m);
		}
		for (reg int i=0;i<n+m;i++) if (find(i)==find(i+n+m)) return 0;
	}
	return 1;
}