#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

/*

*/
// int perform_experiment(vector<int> e){
//     return e.size();
// }

vector<int> find_colours(int n, vector<int> x, vector<int> y){
    vector<int> ans(n);
    vector<int> e, reset(n, -1);

    int sz = 1;
    while(sz < n) sz*=2;

    for(int i = 0; i < n;i++){
        for(int cond = 0; cond < 2;cond++){
            e = reset;
            for(int j = 0; j < n;j++){
                if(j%2==cond) e[j] = i;
            }
            int x = perform_experiment(e);
            if(x == n) continue;
            queue<array<int,6>> q;
            q.push({0, sz/2 - 1, sz/2, x, n, 0});
            while(q.size()){
                auto [l,r,v, previous_x, previous_size, tttt] = q.front();
                q.pop();
                e = reset;
                int curr = l;
                int tt = min(r, n - 1);
                for(int j = l; j <= tt;j++){
                    if(j%2 == cond) e[j] = i;
                }
                for(int j = 0; j < l;j++) e[j] = n;
                for(int j = tt + 1; j < n;j++) e[j] = n;
                x = perform_experiment(e);
                int crs = v/2;
                int add = 2 - (l == 0) - (tt == n-1);
                int current_size = tt - l + 1, current_x = x - add;

                if(tttt == 1 && current_size == current_x) continue;

                if(current_size == 2 && current_x == 1){
                    ans[l + cond] = i;
                    continue;
                }
                
                // if it doesn't contain all of the prev ones then we don't have to put in the other segment 
                if(current_size - current_x == previous_size - previous_x){
                    q.push({l, l + crs - 1, crs, current_x, current_size, 0});
                }
                // if the current x is equal to the size + 1 then the other segment contains everything!
                else if(current_x == current_size){
                    q.push({r + 1, r + v, v, previous_x, previous_size, 1});
                } 
                // check if the current x contains all of the previous ones, if so then we don't have to put in the other segment (only condition remaining)
                else{
                    q.push({l, l + crs - 1, crs, current_x, current_size, 0});
                    q.push({r + 1, r + v, v, previous_x, previous_size, 1});
                }
            }
        }
    }
    return ans;
}

// void solve(){
    
// }

// int main(){
//     ios::sync_with_stdio(false);
//     cin.tie(0);
//     cout.tie(0);
//     int t=1;
//     cin >> t;
//     while(t--) solve();
//     return 0;
// }