#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<vector<pair<int, int>>> chl, chr;
vector<bool> ll;
vector<int> createFunTour(int N, int Q) {
n = N;
q = Q;
ll.assign(n, false);
chl.resize(n);
chr.resize(n);
for (int i = n-1; i >= 1; i--) {
int curr = i;
int dis = 0;
while (curr > 0) {
int par = (curr - 1) / 2;
if (curr % 2) ll[curr] = true;
if (ll[curr]) {
chl[par].push_back({dis+1, i});
}
else chr[par].push_back({dis+1, i});
dis++;
curr = par;
}
}
for (int i = 0; i < n; i++) {
sort(chl[i].begin(), chl[i].end());
sort(chr[i].begin(), chr[i].end());
}
vector<int> perm;
vector<bool> used(n, false);
perm.push_back(n-1);
int curr = n-1;
used[curr] = true;
while (perm.size() < n) {
int mx = 0, goTo = curr;
int dis = 0;
while (chl[curr].size() > 0 && used[chl[curr].back().second]) chl[curr].pop_back();
while (chr[curr].size() > 0 && used[chr[curr].back().second]) chr[curr].pop_back();
if (!chl[curr].empty()) {
mx = chl[curr].back().first;
goTo = chl[curr].back().second;
}
if (!chr[curr].empty() && chr[curr].back().first >= mx) {
mx = chr[curr].back().first;
goTo = chr[curr].back().second;
}
while (curr > 0) {
int par = (curr - 1) / 2;
dis++;
while (chl[par].size() > 0 && used[chl[par].back().second]) chl[par].pop_back();
while (chr[par].size() > 0 && used[chr[par].back().second]) chr[par].pop_back();
if (dis >= mx && !used[par]) {
mx = dis;
goTo = par;
}
if (ll[curr] && !chr[par].empty()) {
int dis2 = chr[par].back().first + dis;
if (dis2 >= mx) {
goTo = chr[par].back().second;
mx = chr[par].back().first + dis;
}
}
else if (!ll[curr] && !chl[par].empty()) {
int dis2 = chl[par].back().first + dis;
if (dis2 >= mx) {
goTo = chl[par].back().second;
mx = chl[par].back().first + dis;
}
}
curr = par;
}
perm.push_back(goTo);
curr = goTo;
used[goTo] = true;
}
return perm;
}
