#include "fun.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define lll __int_128t
#define ll long long
#define ld long double
#define pi pair<int,int>
#define pl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define f first
#define s second
#define vvi vector<vi>
#define vvl vector<vl>
#define setind DEBUG_INDENT =
#define enl "\n";
#define debug(k) for(int _ = 0; _ < DEBUG_INDENT; _ ++) { cout << " "; } cout << #k << ": " << k << enl;
const int MOD = 1e9 + 7;
const ll MODL = 1e9 + 7;
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> pbds;
int DEBUG_INDENT = 0;
std::vector<int> createFunTour(int N, int Q) {
if(N == 2) {
return {0,1};
}
vector<pi> subs(N);
subs[0] = {N,0};
for(int i = 1; i < N; i ++) {
subs[i] = {attractionsBehind(0,i),i};
}
sort(subs.begin(),subs.end());
int idx =0;
while(subs[idx].f < (N+1) / 2) {
idx ++;
}
int cen = subs[idx].s;
vector<int> dis(N);
vector<int> cs;
for(int i = 0; i < N; i ++) {
dis[i] = hoursRequired(cen,i);
if(dis[i] == 1) {
cs.push_back(i);
}
}
if(cs.size() == 2) {
int a = cs[0];
int b = cs[1];
vector<pi> as;
vector<pi> bs;
for(int i = 0; i < N; i ++) {
if(i == cen) { continue; }
if(hoursRequired(b,i) < dis[i]) {
bs.push_back({dis[i],i});
} else {
as.push_back({dis[i],i});
}
}
sort(as.begin(),as.end());
sort(bs.begin(),bs.end());
bool CA = as.size() > bs.size();
vector<int> res;
int ia, ib;
if(CA) {
res = {as[as.size()-1].s};
ia = as.size()-2;
ib = bs.size()-1;
} else {
res = {bs[bs.size()-1].s};
ia = as.size()-1;
ib = bs.size()-2;
}
for(int i = 2; i < N; i ++) {
if(CA) {
res.push_back(bs[ib--].s);
} else {
res.push_back(as[ia--].s);
}
CA = !CA;
}
res.push_back(cen);
// for(int r : res) {
// cout << r << " ";
// }
// cout << endl;
return res;
}
vector<vector<pi>> ps(3);
for(int i = 0; i < N; i ++) {
if(i == cen) { continue; }
if(hoursRequired(cs[0],i) < dis[i]) {
ps[0].push_back({dis[i],i});
} else if(hoursRequired(cs[1],i) < dis[i]) {
ps[1].push_back({dis[i],i});
} else {
ps[2].push_back({dis[i],i});
}
}
sort(ps[0].begin(),ps[0].end());
sort(ps[1].begin(),ps[1].end());
sort(ps[2].begin(),ps[2].end());
int cur = -20;
vector<int> ids(3);
ids[0] = ps[0].size() - 1;
ids[1] = ps[1].size() - 1;
ids[2] = ps[2].size() - 1;
vector<int> res;
int c = 0;
while((ids[0] + ids[1] >= ids[2]) && (ids[0] + ids[2] >= ids[1]) && (ids[2] + ids[1] >= ids[0])) {
c ++;
pair<int,pi> nxt = {0,{-1,-1}};
for(int i = 0; i < 3; i ++) {
if(i == cur) { continue; }
pi node = ps[i][ids[i]];
nxt = max(nxt,{node.f,{node.s,i}});
}
res.push_back(nxt.s.f);
// cout << nxt.s.f << endl;
ids[nxt.s.s] --;
cur = nxt.s.s;
}
// cout << "done" << endl;
if(ids[0] + ids[1] < ids[2]) {
if(cur < 0) { cur = 0; }
while(c < N - 1) {
c ++;
pair<int,pi> nxt = {0,{-1,-1}};
for(int i = 0; i < 3; i ++) {
if(i == cur || (i + cur == 1) || ids[i] < 0) { continue; }
pi node = ps[i][ids[i]];
nxt = max(nxt,{node.f,{node.s,i}});
}
res.push_back(nxt.s.f);
ids[nxt.s.s] --;
cur = nxt.s.s;
}
} else if(ids[0] + ids[2] < ids[1]) {
if(cur < 0) { cur = 0; }
while(c < N - 1) {
c ++;
pair<int,pi> nxt = {0,{-1,-1}};
for(int i = 0; i < 3; i ++) {
if(i == cur || (i + cur == 2) || ids[i] < 0) { continue; }
pi node = ps[i][ids[i]];
nxt = max(nxt,{node.f,{node.s,i}});
}
res.push_back(nxt.s.f);
ids[nxt.s.s] --;
cur = nxt.s.s;
}
} else {
if(cur < 0) { cur = 2; }
while(c < N - 1) {
c ++;
pair<int,pi> nxt = {0,{-1,-1}};
for(int i = 0; i < 3; i ++) {
if(i == cur || (i + cur == 3) || ids[i] < 0) { continue; }
pi node = ps[i][ids[i]];
nxt = max(nxt,{node.f,{node.s,i}});
}
res.push_back(nxt.s.f);
ids[nxt.s.s] --;
cur = nxt.s.s;
}
}
// cout << "C E " << cen << endl;
res.push_back(cen);
// for(int r : res) {
// cout << r << endl;
// }
// cout << "\n";
return res;
}
