#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
std::vector<int> construct_permutation(long long k){
vll bits;
while(k>0){
bits.pb(k%2);
k/=2;
}
deque<ll> ans;
bits.pop_back();
reverse(all(bits));
for(ll i = 0,cur=0; i < bits.size(); ++i){
ans.pb(cur++);
if(bits[i]==1){
ans.push_front(cur++);
}
}
vector<int> ret;
for(ll i:ans)ret.pb(i);
return ret;
}
