#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
const int nax = 5e5+5;
vector<int> mark(int N,int color,int l,int r){
vector<int> ans(N,N);
for (int i = l; i <= r; ++i)
{
if((i-l)%2) ans[i]=color;
else ans[i]=-1;
}
return ans;
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
vector<int> p, imp;
for (int i = 0; i < N; ++i) (i%2 ? imp : p).push_back(i);
vector<int> ans(N);
for (int i = 0; i < N; ++i)
{
int lst=-1;
while(true){
if(lst>p.back()) break;
int cur = lower_bound(p.begin(),p.end(),lst)-p.begin();
int x = perform_experiment(mark(N,i,p[cur],N-1));
if(x-(p[cur]>0)==N-1-p[cur]+1) break;
int r=p.size();
int l=cur-1;
while(r-l>1){
int mid=(r+l)/2;
if(perform_experiment(mark(N,i,p[cur],p[mid]+1))-(p[cur]>0)-(p[mid]+1<N-1)==p[mid]+1-p[cur]+1) l=mid;
else r=mid;
}
ans[p[r]]=i;
lst=p[r]+1;
}
}
for (int i = 0; i < N; ++i)
{
int lst=-1;
while(true){
if(lst>imp.back()) break;
int cur = lower_bound(imp.begin(),imp.end(),lst)-imp.begin();
int x = perform_experiment(mark(N,i,imp[cur],N-1));
if(x-1==N-1-imp[cur]+1) break;
int r=imp.size();
int l=cur-1;
while(r-l>1){
int mid=(r+l)/2;
if(perform_experiment(mark(N,i,imp[cur],min(N-1,imp[mid]+1)))-1-(imp[mid]+1<N-1)==imp[mid]+1-imp[cur]+1) l=mid;
else r=mid;
}
ans[imp[r]]=i;
lst=imp[r]+1;
}
}
return ans;
}
