#include "prg.h"
#include <bits/stdc++.h>
int pa[3009],cl[3009],sz[3009];
inline int fr(int x) {
	while(x!=pa[x]) {
		x=pa[x];
	}
	return pa[x];
}
inline int qq(int x) {
	int as=0;
	while(x!=pa[x]) {
		as^=cl[x];
		x=pa[x];
	}
	return as;
}
int chk(int x,int y,int va) {
	int aa=fr(x);
	int bb=fr(y);
	if(aa==bb) {
		if((qq(x)^qq(y))==va) return 1;
		return 0;
	}
	if(sz[aa]>sz[bb]) std::swap(aa,bb);
	sz[bb]+=sz[aa];
	cl[aa]=(va^qq(x)^qq(y));
	pa[aa]=bb;
	return 1;
}
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 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);
			}
		}
	//	printf("%d\n",vv);
		if(vv<=20000||vv>=55000) return 2;
		return 1; 
	}
	int p[3009],c1=0,c2=0;
	std::mt19937 rng(114);
	for(int i=0;i<25;i++) {
		std::map<int,int> vi;
		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);
			if(vi[1ll*3009*p1+p2]) {
				if(s[i][j]==vi[1ll*3009*p1+p2]-1) c1++;
				else c2++;
			}
			vi[1ll*3009*p1+p2]=s[i][j]+1;
		}
	}
	if(c1>8*c2/7) return 2;
//	printf("%d %d\n",c1,c2);
	return 1;
}