#include<bits/stdc++.h>
#include "workshop.h"

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

const int B=21,M=100000;
int cnt;
int per[100005];
mt19937 mrand(1);

namespace sub1{

const int C=5,N=7;
int pw[10];
int p[1000005],col[1000005],fix[1000005];
vector<int> adj[1000005];
bool vis[1000005];

int id(int x,int y,int z){return (x-1)*N*N+(y-1)*N+z;}

void change(int x){
	int num[C]={0};
	for(auto v:adj[x]) num[col[v]]++;
	vector<int> co(0);
	int mina=1<<30;
	for(int k=0;k<C;k++){
		if(chkmin(mina,num[k])) co.clear(),co.pb(k);
		else if(mina==num[k]) co.pb(k);
	}
	int pl=mrand()%co.size();
	cnt-=num[col[x]];
	cnt+=mina;
	col[x]=co[pl];
}

void work(){
	pw[0]=1;
	for(int i=1;i<=6;i++) pw[i]=pw[i-1]*N;
	for(int i=0;i<N;i++){
		int mask=0;
		for(int j=0;j<6;j++) mask+=pw[j]*i;
		vis[mask]=1;
	}
	for(int i=0;i<pw[6];i++){
		if(vis[i]) continue;
		int t=i/pw[5];
		for(int j=0;j<N;j++){
			int to=i%pw[5]*N+j;
			if(vis[to]) continue;
			adj[i].pb(to);
			adj[to].pb(i);
		}
	}
	for(int i=0;i<pw[6];i++) p[i]=i,fix[i]=-1;
	for(int i=0;i<pw[6];i++){
		int tmp=i/pw[5];
		bool fl=0;
		for(int j=1;j<6;j++) if(i/pw[j]%N!=tmp) fl=1;
		if(!fl) fix[i]=0;
	}
	for(int i=0;i<pw[6];i++){
		int tmp=i%N;
		bool fl=0;
		for(int j=0;j<5;j++) if(i/pw[j]%N!=tmp) fl=1;
		if(!fl) fix[i]=1;
	}
	while(1){
		cnt=0;
		for(int i=0;i<pw[6];i++){
			col[i]=mrand()%C;
			if(fix[i]>=0) col[i]=fix[i];
		}
		for(int i=0;i<pw[6];i++) for(auto v:adj[i]) if(col[i]==col[v]) cnt++;
		cnt>>=1;
		for(int i=1;i<=1000;i++){
			// cout<<"cnt "<<cnt<<endl;
			shuffle(p,p+pw[6],mrand);
			for(int i=0;i<pw[6];i++) if(fix[p[i]]<0) change(p[i]);
			if(!cnt) break;
		}
		if(!cnt) break;
	}
}

}

namespace sub2{

const int C=3,N=3;
int pw[10];
int p[1000005],col[1000005];
vector<int> adj[1000005];
bool vis[1000005];

int id(int x,int y,int z){return (x-1)*N*N+(y-1)*N+z;}

void change(int x){
	int num[C]={0};
	for(auto v:adj[x]) num[col[v]]++;
	vector<int> co(0);
	int mina=1<<30;
	for(int k=0;k<C;k++){
		if(chkmin(mina,num[k])) co.clear(),co.pb(k);
		else if(mina==num[k]) co.pb(k);
	}
	int pl=mrand()%co.size();
	cnt-=num[col[x]];
	cnt+=mina;
	col[x]=co[pl];
}

void work(){
	pw[0]=1;
	for(int i=1;i<=6;i++) pw[i]=pw[i-1]*N;
	for(int i=0;i<N;i++){
		int mask=0;
		for(int j=0;j<6;j++) mask+=pw[j]*i;
		vis[mask]=1;
	}
	for(int i=0;i<pw[6];i++){
		if(vis[i]) continue;
		int t=i/pw[5];
		for(int j=0;j<N;j++){
			int to=i%pw[5]*N+j;
			if(vis[to]) continue;
			adj[i].pb(to);
			adj[to].pb(i);
		}
	}
	for(int i=1;i<=pw[6];i++) p[i]=i;
	while(1){
		cnt=0;
		for(int i=1;i<=pw[6];i++) col[i]=mrand()%C;
		for(int i=1;i<=pw[6];i++) for(auto v:adj[i]) if(col[i]==col[v]) cnt++;
		cnt>>=1;
		for(int i=1;i<=1000;i++){
			// cout<<"cnt "<<cnt<<endl;
			shuffle(p+1,p+pw[6]+1,mrand);
			for(int i=1;i<=pw[6];i++) change(p[i]);
			if(!cnt) break;
		}
		if(cnt<=15) break;
	}
}

}

void init(){
	for(int i=0;i<M;i++) per[i]=i;
	shuffle(per,per+M,mrand);
	sub1::work();
	sub2::work();
}

int morning(int my_num,int right_num){
	return per[my_num]%B*B+per[right_num]%B;
}

int afternoon(int left_num, int my_num, int right_num){
	int t1=left_num/B;
	int t2=my_num/B;
	int t3=right_num/B;
	int t4=right_num%B;
	return t1*B*B*B+t2*B*B+t3*B+t4;
}

int evening(int left_num, int my_num, int right_num){
	int b=sub1::N,tb=sub2::N;
	int t1=left_num/B/B/B;
	int t2=my_num/B/B/B;
	int t3=right_num/B/B/B;
	int t4=right_num%(B*B*B)/B/B;
	int t5=right_num%(B*B)/B;
	int t6=right_num%B;
	int a1=t1%b;
	int a2=t2%b;
	int a3=t3%b;
	int a4=t4%b;
	int a5=t5%b;
	int a6=t6%b;
	int b1=t1/b;
	int b2=t2/b;
	int b3=t3/b;
	int b4=t4/b;
	int b5=t5/b;
	int b6=t6/b;
	int mask1=a1*b*b*b*b*b+a2*b*b*b*b+a3*b*b*b+a4*b*b+a5*b+a6;
	int mask2=b1*tb*tb*tb*tb*tb+b2*tb*tb*tb*tb+b3*tb*tb*tb+b4*tb*tb+b5*tb+b6;
	int ret=0;
	if(sub1::vis[mask1]) ret=sub2::col[mask2]+2;
	else ret=sub1::col[mask1];
	return ret;
}