#include <bits/stdc++.h>
#include "perm.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
vector <int> construct_permutation(ll k) {
vector <int> v;
for (int i = 58, j = 0, jj = 0; i >= 0; i -= 2) {
int x = (k >> i) & 3;
if (!j) {
if (!x) continue;
j = 1;
if (x == 2) v.pb(0);
else if (x == 3) v.pb(1), v.pb(0), jj = 1;
}
else {
int mx = -1;
for (int y : v) mx = max(mx, y);
if (!x) v.pb(mx+1), v.pb(mx+2);
else if (x == 1) {
v.pb(mx+1);
v.pb(mx+2);
for (int& y : v) y++;
v.pb(0);
}
else if (x == 2) {
v.pb(mx+1);
for (int& y : v) y++;
v.pb(0);
v.pb(mx+3);
}
else if (!jj) {
jj = 1;
for (int& y : v) y += 2;
v.pb(mx+3);
v.pb(1);
v.pb(mx+4);
v.pb(0);
}
else {
for (int& y : v) if (y >= 2) y++;
v.pb(mx+2);
v.pb(mx+3);
v.pb(2);
}
}
}
return v;
}
