#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define vp vector<pp>
vector<int> small(int n, std::vector<int> x, std::vector<int> y){
vector<int> ans(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
vector<int> query(n, j);
query[i] = -1;
ll x = perform_experiment(query);
if(x == 1){
ans[i] = j;
break;
}
}
}
return ans;
}
vector<int> complete(int n, vector<int> x, vector<int> y){
vector<int> ans(n);
for(int i = 0; i < n; i++){
ll l = 0, r = n;
while(l < r - 1){
vector<int> query(n, n);
query[i] = -1;
ll s = (l + r)/2;
ll ind = l;
for(int j = 0; j < n; j++){
if(i == j) continue;
query[j] = ind;
ind++;
if(ind == s) break;
}
ll x = perform_experiment(query);
if(x == s - l + 1) r = s;
else l = s;
}
ans[i] = l;
}
return ans;
}
vector<int> sedL(ll n, ll l, ll r, ll c){
vector<int> ans(n, n);
for(int i = l; i < r; i++){
if(i % 2 == 1){
ans[i] = c;
}else{
ans[i] = -1;
}
}
return ans;
}
vector<int> sedS(ll n, ll l, ll r, ll c){
vector<int> ans(n, n);
for(int i = l; i < r; i++){
if(i % 2 == 0){
ans[i] = c;
}else{
ans[i] = -1;
}
}
return ans;
}
vector<int> find_colours(int n, std::vector<int> x, std::vector<int> y) {
if(n <= 50) return small(n, x, y);
if(x.size() == n*(n - 1) / 2) return complete(n, x, y);
vector<int> ans(n);
for(int i = 0; i < n; i++){
ll beg = 0;
while(true){
ll l = beg, r = n;
if(l >= r) break;
bool spec = false;
if(l == n - 1) {
l--;
spec = true;
}
vector<int> query = sedL(n, l, r, i);
ll x = perform_experiment(query);
ll expected = r - l + 2;
if(l == 0) expected--;
if(r == n) expected--;
if(expected != x){
while(r - l > 2){
ll s = (l + r) / 2;
if(s % 2 == 1) s++;
query = sedL(n, l, s, i);
x = perform_experiment(query);
expected = s - l + 2;
if(l == 0) expected--;
if(s == n) expected--;
if(x == expected) l = s;
else r = s;
if(l % 2 == 1) l++;
if(r % 2 == 0) r--;
}
if(spec) {
ans[l + 1] = i;
break;
}
ans[l] = i;
beg = l + 2;
}else{
break;
}
}
beg = 0;
while(true){
ll l = beg, r = n;
if(l >= r) break;
bool spec = false;
if(l == n - 1) {
l--;
spec = true;
}
vector<int> query = sedS(n, l, r, i);
ll x = perform_experiment(query);
ll expected = r - l + 2;
if(l == 0) expected--;
if(r == n) expected--;
if(expected != x){
while(r - l > 2){
ll s = (l + r) / 2;
if(s % 2 == 0) s++;
query = sedS(n, l, s, i);
x = perform_experiment(query);
expected = s - l + 2;
if(l == 0) expected--;
if(s == n) expected--;
if(x == expected) l = s;
else r = s;
if(l % 2 == 0) l++;
if(r % 2 == 1) r--;
}
if(spec) {
ans[l + 1] = i;
break;
}
ans[l] = i;
beg = l + 2;
}else{
break;
}
}
/*while(l < r - 1){
vector<int> query(n, n);
query[i] = -1;
ll s = (l + r)/2;
ll ind = l;
for(int j = 0; j < n; j++){
if(i == j) continue;
query[j] = ind;
ind++;
if(ind == s) break;
}
ll x = perform_experiment(query);
if(x == s - l + 1) r = s;
else l = s;
}
ans[i] = l;*/
}
return ans;
}
