#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
int bs( int n, int val, int t, vector<int> &resp ){
int l = 0, r = n - 1;
while( l < r ){
int mid = ( l + r )/2;
int aux = (( val == n - 1 ) ? val - 1 : val + 1 );
vector<int> v(n, n);
for( int i = 0; i < n; i++ ){
if( i%2 != t ) v[i] = val;
else if( i < l || mid < i ) v[i] = aux;
else if( resp[i] != -1 ) v[i] = aux;
else v[i] = -1;
}
if( perform_experiment(v) == n ) l = mid + 1;
else r = mid;
}
return r;
}
void solve( int t, vector<int> &resp ){
int n = resp.size();
for( int i = 0; i < n; i++ ){
while( true ){
int aux = (( i == n - 1 ) ? i - 1 : i + 1 );
vector<int> v(n, i);
for( int j = 0; j < n; j++ ){
if( j%2 == t ) v[j] = (( resp[j] == -1 ) ? -1 : aux );
}
if( perform_experiment(v) == n ) break;
resp[bs( n, i, t, resp )] = i;
}
}
}
vector<int> find_colours(int n, vector<int> a, vector<int> b) {
vector<int> resp(n, -1);
solve( 0, resp );
solve( 1, resp );
return resp;
}
