#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> C, num;
void solve(int l, int r, int c){
if (r < l) return;
int p = (l % 2);
if (r % 2 != p) r--;
//cout << l << " " << r << " " << c << endl;
if (l == 0){
vector<int> v(N, N);
v[l] = -1;
v[l+1] = c;
if (C[l] == -1 && perform_experiment(v) < min(N, 3)){
C[l] = c;
num[c]++;
}
solve(l+2, r, c);
return;
}
if (r == N-1){
vector<int> v(N, N);
v[r] = -1;
v[r-1] = c;
if (C[r] == -1 && perform_experiment(v) < min(N, 3)){
C[r] = c;
num[c]++;
}
solve(l, r-2, c);
return;
}
int x = 0;
for (int i=l; i<=r; i++) x += (C[i] == -1);
if (x == 0) return;
vector<int> v(N, N);
for (int i=l; i<=r; i+=2) v[i] = -1;
for (int i=1-p; i<N; i+=2) v[i] = c;
int res = perform_experiment(v);
int z = (N-res)/2;
if (z == 0) return;
if (z == x){
num[c] += z;
for (int i=l; i<=r; i+=2){
if (C[i] == -1) C[i] = c;
}
return;
}
int exp = num[c]+z;
int m = (l+r)/2;
if (m % 2 != p) m--;
solve(l, m, c);
if (num[c] != exp) solve(m+2, r, c);
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y){
::N = N;
C.resize(N, -1);
num.resize(N, 0);
for (int i=0; i<N; i++){
solve(0, N-1, i);
solve(1, N, i);
}
return C;
}
