#include"prg.h"
#include<vector>
#include<cmath>
#include<ctime>
#include<cstdlib>
using namespace std;
double solve(int n,int m,double p)
{
	double a=1,b=1,c=1,d=1;
	for(int i=0;i<m;i++){
		a*=p; c*=1-p;
	}
	for(int i=0;i<n-m;i++){
		b*=1-p; d*=p;
	}
	return log2(a*b+c*d);
}

vector<int> to[1000],id[1000];
vector<int> ed[1000][1000];

int solve(int n,int m,int k,vector<int> op,array<vector<int>,3000> arr,int T,array<array<int,3000>,25> res)
{
	if(op[k-2]!=2){
		int cnt=0;
		for(int i=0;i<T;i++)
			for(int j=0;j<m;j++)
				cnt+=res[i][j];
		if(cnt<35000||cnt>40000)
			return 2;
		return 1;
	}
	for(int i=0;i<n;i++)
		id[i].clear();
	if(k<4||op[1]!=2){
		double p1=0.5,p2=0.75;
		if(k==4&&op[0]!=2&&op[1]!=2){
			if(op[1]==op[2]) p2=0.875;
			else p2=0.625;
		}
		double E1=0.0,E2=0.0;
		for(int i=0;i<m;i++)
			id[arr[i][k-1]].push_back(i);
		for(int i=0;i<n;i++)
			for(int t=0;t<T;t++){
				int p=id[i].size(),cnt=0;
				for(int j=0;j<p;j++)
					cnt+=res[t][id[i][j]];
				E1+=solve(p,cnt,p1);
				E2+=solve(p,cnt,p2);
			}
		if(E2>E1) return 2;
		return 1;
	}
	double E1=0.0,E2=0.0;
	for(int i=0;i<n;i++){
		to[i].clear();
		for(int j=i;j<n;j++)
			ed[i][j].clear();
	}
	for(int i=0;i<m;i++){
		int a=arr[i][2],b=arr[i][3];
		to[a].push_back(b);
		to[b].push_back(a);
		id[a].push_back(i);
		id[b].push_back(i);
		if(a>b) swap(a,b);
		ed[a][b].push_back(i);
	}
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
			if(ed[i][j].size()>=2){
				int c0=ed[i][j][0],c1=ed[i][j][1];
				for(int t=0;t<T;t++){
					E2-=1.0;
					if(res[t][c0]==res[t][c1]) E1+=log2(0.625);
					else E1+=log2(0.375);
				}
			}
	double U=log2(0.5625),V=log2(0.4375);
	for(int i=0;i<n;i++)
		for(int j=0;j<to[i].size();j++)
			for(int k=j+1;k<to[i].size();k++){
				int x=to[i][j],y=to[i][k];
				if(x>y) swap(x,y);
				if(ed[x][y].size()>=1){
					int a=ed[x][y][0];
					int b=id[i][j],c=id[i][k];
					for(int t=0;t<T;t++){
						int v=res[t][a]^res[t][b]^res[t][c];
						E2-=1.0;
						if(op[0]^v) E1+=V;
						else E1+=U;
					}
				}
			}
	U=log2(15.0/32); V=log2(17.0/32);
	U*=1.01; V*=1.01;
	for(int i=0;i<n;i++)
		for(int j=i;j<n;j++)
			ed[i][j].clear();
	for(int i=0;i<n;i++)
		for(int j=0;j<to[i].size();j++)
			for(int k=j+1;k<to[i].size();k++){
				int x=to[i][j],y=to[i][k];
				if(x>y) swap(x,y);
				ed[x][y].push_back(id[i][j]*m+id[i][k]);
			}
			double W1=E1,W2=E2;
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
			if(ed[i][j].size()>=2){
				int a=ed[i][j][0]/m,b=ed[i][j][0]%m;
				int c=ed[i][j][1]/m,d=ed[i][j][1]%m;
				for(int t=0;t<T;t++){
					int v=res[t][a]^res[t][b]^res[t][c]^res[t][d];
					E2--;
					if(v==1) E1+=U;
					else E1+=V;
				}
			}
	if(E1>E2) return 2;
	return 1;
}