#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const int mxN=1e5+5;
const int LOG=20;
vector<pair<int, int>> v[mxN][2];
bool done[mxN];
int d[mxN];
}
vector<int> createFunTour(int n, int q) {
memset(done, 0, sizeof(done));
for(int i=1;i<=n;i++){
d[i]=0;
int tar=i;
tar/=2;
while(tar>0){
d[i]++;
tar/=2;
}
}
for(int i=1;i<=n;i++){
int tar=i/2;
int pre=i;
while(tar>0){
if(pre==2*tar){
v[tar][0].pb({d[i]-d[tar], i});
}
else{
v[tar][1].pb({d[i]-d[tar], i});
}
pre=tar;
tar/=2;
}
}
int mx=0, idx=0;
for(int i=1;i<=n;i++){
if(d[i]>mx){
mx=d[i];
idx=i;
}
}
int cur=idx;
vector<int> ans(n);
auto f=[&](int it){
int tar=it/2;
int pre=it;
mx=-1, idx=-1;
for(int i=0;i<2;i++){
while(!v[it][i].empty() && done[v[it][i].back().S]){
v[it][i].pop_back();
}
if(!v[it][i].empty()){
if(v[it][i].back().F>mx){
mx=v[it][i].back().F;
idx=v[it][i].back().S;
}
}
}
while(tar>0){
if(d[it]-d[tar]>mx){
mx=d[it]-d[tar];
idx=tar;
}
if(pre==2*tar){
while(!v[tar][1].empty() && done[v[tar][1].back().S]){
v[tar][1].pop_back();
}
if(!v[tar][1].empty()){
if(d[it]-d[tar]+v[tar][1].back().F>mx){
mx=d[it]-d[tar]+v[tar][1].back().F;
idx=v[tar][1].back().S;
}
}
}
else{
while(!v[tar][0].empty() && done[v[tar][0].back().S]){
v[tar][0].pop_back();
}
if(!v[tar][0].empty()){
if(d[it]-d[tar]+v[tar][0].back().F>mx){
mx=d[it]-d[tar]+v[tar][0].back().F;
idx=v[tar][0].back().S;
}
}
}
pre=tar;
tar/=2;
}
return idx;
};
for(int rep=0;rep<n;rep++){
ans[rep]=cur-1;
done[cur]=1;
cur=f(cur);
}
// for(auto &it:ans){
// cout<<it<<' ';
// }
// cout<<'\n';
return ans;
}
