#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> construct_permutation(ll k){
vector<ll> b4;
while (k){
b4.push_back(k & 3); k >>= 2;
}
int sz = b4.size();
vector<int> vec;
if (b4[sz - 1] == 2) vec = {0};
else if (b4[sz - 1] == 3) vec = {1, 0};
for (int i = sz - 2; i >= 0; i--){
int amt = vec.size();
if (b4[i] == 0){
vec.push_back(amt); vec.push_back(amt + 1);
}
else if (b4[i] == 1){
vec.push_back(amt); vec.push_back(amt + 1); vec.insert(vec.begin(), amt + 2);
}
else if (b4[i] == 2){
vec.push_back(amt); vec.push_back(amt + 2); vec.insert(vec.begin(), amt + 1);
}
else{
if (vec.size() >= 2 && vec[0] > vec[1]){
vec.push_back(amt); vec.push_back(amt + 1); vec.insert(vec.begin() + 2, amt + 2);
}
else{
vec.push_back(amt); vec.push_back(amt + 2); vec.insert(vec.begin(), amt + 1); vec.insert(vec.begin(), amt + 3);
}
}
}
return vec;
}
