#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 252
int find_ch(int le, int re, int col)
{
int N=re+1;
if (le>re) return -1;
if (le==re && le%2==1) return -1;
if (le==re)
{
vector<int> E(N, N);
E[le]=-1;
E[le-1]=col;
int xx=perform_experiment(E);
if (N==2)
{
if (xx==2) return -1;
else return le;
}
else
{
if (xx==3) return -1;
else return le;
}
}
vector<int> E(N);
int ochr=re-le+1;
if (le!=0) ochr++;
for (int q=0;q<le;q++) E[q]=N;
for (int q=le;q<=re;q++)
{
if (q%2==0) E[q]=-1;
else E[q]=col;
}
int xx=perform_experiment(E);
if (xx==ochr) return -1;
int l=le-1,r=re;
while (l<r-1)
{
int mid=(l+r)/2;
ochr=mid-le+1;
if (mid==le)
{
r=mid;
continue;
}
if (mid!=N-1) ochr++;
if (le!=0) ochr++;
for (int q=0;q<le;q++) E[q]=N;
for (int q=le;q<=mid;q++)
{
if (q%2==0) E[q]=-1;
else E[q]=col;
}
for (int q=mid+1;q<N;q++)
{
E[q]=N;
}
xx=perform_experiment(E);
if (xx==ochr) l=mid;
else r=mid;
}
return r;
}
int find_nc(int le, int re, int col)
{
int N=re+1;
if (le>re) return -1;
if (le==re && le%2==0) return -1;
if (le==re)
{
vector<int> E(N, N);
E[le]=-1;
E[le-1]=col;
int xx=perform_experiment(E);
if (N==2)
{
if (xx==2) return -1;
else return le;
}
else
{
if (xx==3) return -1;
else return le;
}
}
vector<int> E(N);
int ochr=re-le+1;
if (le!=0) ochr++;
for (int q=0;q<le;q++) E[q]=N;
for (int q=le;q<=re;q++)
{
if (q%2==1) E[q]=-1;
else E[q]=col;
}
int xx=perform_experiment(E);
if (xx==ochr) return -1;
int l=le-1,r=re;
while (l<r-1)
{
int mid=(l+r)/2;
ochr=mid-le+1;
if (mid==le)
{
r=mid;
continue;
}
if (mid!=N-1) ochr++;
if (le!=0) ochr++;
for (int q=0;q<le;q++) E[q]=N;
for (int q=le;q<=mid;q++)
{
if (q%2==1) E[q]=-1;
else E[q]=col;
}
for (int q=mid+1;q<N;q++)
{
E[q]=N;
}
xx=perform_experiment(E);
if (xx==ochr) l=mid;
else r=mid;
}
return r;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
vector<int> G(N, -1);
for (int col=0;col<=N-1;col++)
{
int ll=0;
while (true)
{
int toi=find_ch(ll,N-1,col);
if (toi==-1) break;
assert(G[toi]==-1);
G[toi]=col;
ll=toi+2;
}
ll=1;
while (true)
{
int toi=find_nc(ll,N-1,col);
if (toi==-1) break;
assert(G[toi]==-1);
G[toi]=col;
ll=toi+2;
}
}
return G;
}
