#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) begin(x), end(x)
const int N = 100000;
vector<int> g[N];
int sz[N];
set<int> st[N], stt[N];
int depth[N];
bool used[N];
void calc_sz(int v, int p) {
sz[v] = 1;
for (int to: g[v]) {
if (to != p && !used[to]) {
calc_sz(to, v);
sz[v] += sz[to];
}
}
}
int centroid(int v, int p, int n) {
for (int to: g[v]) {
if (to != p && !used[to] && sz[to] * 2 > n)
return centroid(to, v, n);
}
return v;
}
void dfs(int v, int p, int leader) {
depth[v] = depth[p] + 1;
st[leader].insert(v);
stt[leader].insert(v);
// cout << v << " " << depth[v] << endl;
for (int to: g[v]) {
if (to != p) {
dfs(to, v, leader);
}
}
}
vector<int> createFunTour(int n, int q) {
const int infI = 1e9 + 7;
if (n <= 500) {
vector<vector<int>> dist(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
dist[i][j] = dist[j][i] = hoursRequired(i, j);
}
}
int j = 0;
pair<int, int> mxx = {-infI, -infI};
for (; j < n; ++j) {
mxx = max(mxx, make_pair(dist[j][0], j));
}
j = mxx.second;
vector<int> ans;
vector<bool> usd(n);
int lst = infI;
for (int k = 0; k < n; ++k) {
ans.push_back(j);
usd[j] = true;
pair<int, int> mx = {-infI, -infI};
for (int z = 0; z < n; ++z) {
if (!usd[z] && dist[j][z] <= lst) {
mx = max(mx, make_pair(dist[j][z], z));
}
}
if (mx.first == -infI) {
break;
}
lst = mx.first;
j = mx.second;
}
if (ans.size() == n) {
return ans;
}
assert(false);
return {};
} else {
for (int i = 1; i < n; ++i) {
g[i].push_back((i - 1) >> 1);
g[(i - 1) >> 1].push_back(i);
}
calc_sz(0, -1);
int c = centroid(0, -1, n);
auto cmp = [](int i, int j) {
if (st[i].empty() && st[j].empty()) return i < j;
else if (st[i].empty()) return false;
else if (st[j].empty()) return true;
else {
int a = *st[i].rbegin(), b = *st[j].rbegin();
if (depth[a] != depth[b]) return depth[a] > depth[b];
return i < j;
}
};
set<int, decltype(cmp)> nw(cmp);
for (int to: g[c]) {
dfs(to, c, to);
nw.insert(to);
}
vector<int> ans;
int mv = 1;
while (!nw.empty()) {
int a = *nw.begin();
// cout << nw.size() << endl;
if (st[a].empty()) {
break;
}
if (ans.empty() || !stt[a].count(ans.back())) {
nw.erase(a);
ans.push_back(*st[a].rbegin());
st[a].erase(prev(st[a].end()));
// cout << nw.size() << endl;
if (!st[a].empty())
nw.insert(a);
} else {
assert(nw.size() > 1);
int b = *next(nw.begin());
assert(!st[b].empty());
a = b;
nw.erase(a);
ans.push_back(*st[a].rbegin());
st[a].erase(prev(st[a].end()));
if (!st[a].empty())
nw.insert(a);
}
}
ans.push_back(c);
return ans;
}
}
