//#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
vector<long long>pw;
unordered_map<long long ,vector<int>>mp;
vector<int>solve(long long k){
if(mp.count(k)!=0){
return mp[k];
}
//cout<<k<<endl;
if(k==0){
mp[k]={};
return {};
}
if(k==1){
mp[k]={0};
return {0};
}
if(k==2){
mp[k]={1,0};
return {1,0};
}
if(k==4){
mp[k]={1,2,0};
return {1,2,0};
}
if(k==5){
mp[k]={0,2,1};
return {0,2,1};
}
if(k==6){
mp[k]={2,3,0,1};
return {2,3,0,1};
}
if(k==7){
mp[k]={0,1,2};
return {0,1,2};
}
if(k==8){
mp[k]={1,2,3,0};
return {1,2,3,0};
}
for(int i=1;i<62;i++){
if(pw[i]==k){
vector<int>ret;
for(int j=0;j<i;j++){
ret.push_back(j);
}
mp[k]=ret;
return ret;
}
}
int last=0,mina=10000000;
for(int i=1;i<62;i++){
if(pw[i]>k){
break;
}
if(pw[i]*pw[i]<k/200000000000000ll){
continue;
}
long long dis=(k+1)/(pw[i]+1);
vector<int>fake=solve(dis-1);
dis=k+1-(pw[i]+1)*dis;
vector<int>fakea=solve(dis);
if(i+(int)fake.size()+(int)fakea.size()<mina){
last=i;
mina=i+(int)fake.size()+(int)fakea.size();
}
}
//cout<<last<<endl;
vector<int>ghabl,bad,now,ret;
long long dis=(k+1)/(pw[last]+1);
long long ferghabl=dis-1,ferbad;
ghabl=solve(ferghabl);
ferbad=k+1-(pw[last]+1)*dis;
bad=solve(ferbad);
for(int i=0;i<last;i++){
now.push_back(i);
}
int szbad=bad.size();
int szghabl=ghabl.size();
for(auto x:ghabl){
ret.push_back(szbad+x);
}
for(auto x:now){
ret.push_back(x+szghabl+szbad);
}
for(auto x:bad){
ret.push_back(x);
}
mp[k]=ret;
return ret;
}
vector<int> construct_permutation(long long k)
{
k--;
pw.resize(62);
for(int i=0;i<62;i++){
pw[i]=(1ll<<i)-1;
}
vector<int>res=solve(k);
//for(auto x:res){
// cout<<x<<" ";
//}
//cout<<endl;
return res;
}
