#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void add_max(vector<int> &p) {
int n = (int) p.size();
p.push_back(n);
}
void add_min(vector<int> &p) {
for (int &x : p)
x++;
p.push_back(0);
}
void add_third(vector<int> &p) {
for (int &x : p)
if (x > 1)
x++;
p.push_back(2);
}
bool condition(vector<int> &p) {
if (p.size() < 2) return false;
int pos1 = -1, pos0 = -1;
for (int i = 0; i < (int) p.size(); i++)
if (p[i] == 0) pos0 = i;
else if (p[i] == 1) pos1 = i;
return pos1 < pos0;
}
vector<int> construct_permutation(ll k) {
int h = 0;
while ((1ll << (h + 1)) <= k)
h++;
vector<int> p;
for (int i = h - 2; i >= 0; i -= 2) {
int val = (k >> i) & 3;
if (val == 0) {
add_max(p);
add_max(p);
} else if (val == 1) {
add_max(p);
add_max(p);
add_min(p);
} else if (val == 2) {
add_max(p);
add_min(p);
add_max(p);
} else if (val == 3) {
if (condition(p)) {
add_max(p);
add_max(p);
add_third(p);
} else {
add_max(p);
add_min(p);
add_max(p);
add_min(p);
}
}
}
if (h % 2 != 0) {
add_max(p);
if (k & 1) add_min(p);
}
return p;
}
