#include<bits/stdc++.h>
//#include "perm.h"
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define sz(x) (int)x.size()
#define pb push_back
vector<int> construct_permutation(long long k){
bool ok=0;
int msb;
vector<int> ans;
for(int i=60;i>0;i--){
if(!ok && !(k & (1LL<<i))) continue;
if(!ok){
ok=1;
msb=i;
if((k & (1LL<<(i-1)))) ans={1,0}; //resposta 3
else ans={0};
i--;
continue;
}
int mask=0;
if((k&(1LL<<i))) mask+=2;
if((k&(1LL<<(i-1)))) mask++;
if(!mask){
int x=sz(ans);
ans.pb(x); ans.pb(x+1);
}
else if(mask==1){
for(auto &x:ans) x++;
int x=sz(ans);
ans.pb(x+1); ans.pb(x+2); ans.pb(0);
}
else if(mask==2){
for(auto &u:ans) u++;
int x=sz(ans);
ans.pb(x+1); ans.pb(0); ans.pb(x+2);
}
else{
int p0=300,p1=300;
fall(i,0,sz(ans)-1){
if(ans[i]==0) p0=i;
if(ans[i]==1) p1=i;
}
if(p0>p1){
for(auto &u:ans) if(u>=2) u++;
int x=sz(ans);
ans.pb(x+1); ans.pb(x+2); ans.pb(2);
}
else{
for(auto &u:ans){
if(u>=2) u++;
u++;
}
int x=sz(ans);
ans.pb(x+2); ans.pb(x+3); ans.pb(2); ans.pb(0);
}
}
i--;
}
if(msb%2==0){
if(k%2==0){
int x=sz(ans); ans.pb(x);
}
else{
for(auto &u:ans) u++;
int x=sz(ans); ans.pb(x+1); ans.pb(0);
}
}
return ans;
}
