#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(ll k, int b, bool f, vector < int > &a){
if(b <= 0) return;
b -= 2;
if(b == -1){
a.push_back(a.size());
if(k & 1){
for(int &x : a) x++;
a.push_back(0);
}
return;
}
int t = (k >> b) & 3;
if(a.empty()){
if(t == 2) a = {0};
else a = {1, 0}, f = 1;
}
else{
if(t == 0){
a.push_back(a.size());
a.push_back(a.size());
}
else if(t == 1){
a.push_back(a.size());
a.push_back(a.size());
for(int &x : a) x++;
a.push_back(0), f = 1;
}
else if(t == 2){
a.push_back(a.size());
for(int &x : a) x++;
a.push_back(0);
a.push_back(a.size()), f = 1;
}
else if(f){
a.push_back(a.size());
a.push_back(a.size());
for(int &x : a)
if(x > 1)
x++;
a.push_back(2);
}
else{
a.push_back(a.size());
for(int &x : a) x++;
a.push_back(0);
a.push_back(a.size());
for(int &x : a) x++;
a.push_back(0);
f = 1;
}
}
solve(k, b, f, a);
}
vector < int > a;
vector < int > construct_permutation(ll k){
a.clear(), solve(k, 64 - __builtin_clzll(k), 0, a);
return a;
}
