#include "prg.h"
#include <bits/stdc++.h>
int hd[1009],to[3009],nxt[3009],val[3009],kk;
void l(int u,int v,int w) {
	to[++kk]=v;nxt[kk]=hd[u];val[kk]=w;hd[u]=kk;
}
std::array<std::vector<int>, 3000>  xt;
int K;
bool cmp(int a,int b) {
	return std::max(xt[a][K-1],xt[a][K-2])<std::max(xt[b][K-1],xt[b][K-2]);
}
int vii[2][2000009];
int solve(int n, int m, int k, std::vector<int> op, std::array<std::vector<int>, 3000> x, 
	int c, std::array<std::array<int, 3000>, 25> s) {
	K=k;xt=x;
	int as=0;
	for(int i=1;i<=25;i++) {
		for(int j=1;j<=3000;j++) {
			if(s[i-1][j-1]==1) as++;
		}
	}
	if(op[k-2]!=2) {
		if(as>=35000&&as<=40000) return 1;
		return 2;
	}
	if(op[k-3]!=2) {
		int vv=0;
		std::vector<int> t[1009];
		for(int j=1;j<=25;j++) {
			int as=0;
			for(int i=0;i<=1000;i++) t[i]=t[1001];
			for(int i=1;i<=3000;i++) {
				t[x[i-1][k-1]].push_back(i);
				if(s[j-1][i-1]==1) as++;
			}
			for(int i=0;i<=1000;i++) {
				int as=0;
				for(int jj=0;jj<t[i].size();jj++) {
					as+=s[j-1][t[i][jj]-1];
				}
				vv+=std::min(as,(signed)t[i].size()-as);
			}
		}
		if(vv<=20000||vv>=55000) return 2;
		return 1; 
	}
	int p[3009],c1=0,c2=0,vi[1009]={0},v2[1009]={0},tt=0,c3=0,c4=0,c5=0,c6=0;
	std::mt19937 rng(114);
	for(int i=0;i<25;i++) {
		for(int j=0;j<1000;j++) hd[j]=0;
		kk=0;
		for(int j=0;j<3000;j++) {
			int p1=x[j][k-1],p2=x[j][k-2];
			if(p1>p2) std::swap(p1,p2);
			int ss=1009*p1+p2;
			c3+=vii[s[i][j]][ss];
			c4+=vii[1-s[i][j]][ss];
			vii[s[i][j]][ss]++;
			l(p1,p2,(s[i][j]^op[0]));
		}
		for(int j=0;j<3000;j++) {
			int p1=x[j][k-1],p2=x[j][k-2];
			if(p1>p2) std::swap(p1,p2);
			int ss=1009*p1+p2;
			vii[s[i][j]][ss]=0;
		}
		for(int i=0;i<1000;i++) {
			tt++;
			for(int j=hd[i];j;j=nxt[j]) {
				vi[to[j]]=tt;
				v2[to[j]]=val[j];
			}
			for(int j=hd[i];j;j=nxt[j]) {
				for(int k=hd[to[j]];k;k=nxt[k]) {
					if(vi[to[k]]==tt) {
						if((val[j]^val[k]^v2[to[k]])==0) c1++;
						else c2++;
					}
					for(int l=hd[to[k]];l;l=nxt[l]) {
						if(vi[to[l]]==tt) {
							if((val[j]^val[k]^val[l]^v2[to[l]])==0) c5++;
							else c6++;
						}
					}
				}
			}
		}
	}
	long double g1=1;
	while(c1||c2) {
		if(((c1==0)||(g1>1))&&c2) {
			c2--;
			g1=g1*7/8;
		} else {
			c1--;
			g1=g1*9/8;
		} 
	}
	while(c3||c4) {
		if(((c3==0)||(g1>1))&&c4) {
			c4--;
			g1=g1*3/4;
		} else {
			c3--;
			g1=g1*5/4;
		} 
	}
	while(c5||c6) {
		if(((c5==0)||(g1>1))&&c6) {
			c6--;
			g1=g1*15/16;
		} else {
			c5--;
			g1=g1*17/16;
		} 
	}
	if(g1>=1) return 2;
	return 1;
}