#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
void append(vector<int>& v, int x, bool bk = 1) {
map<int, int> e;
for (int& a : v) {
if (a > x) a++;
e[a]++;
}
for (int i = 0;; i++) if (!e.count(i)) {
if (bk) v.push_back(i);
else v.insert(v.begin(), i);
break;
}
}
const int big = 100000;
const int small = -1;
std::vector<int> construct_permutation(long long k) {
vector<int> ops;
while (k) {
ops.push_back(k % 4);
k /= 4;
}
reverse(ops.begin(), ops.end());
vector<int> p;
for (int i : ops) {
if (p.empty()) {
if (i == 1) p = {};
else if (i == 2) p = {0};
else if (i == 3) p = {1, 0};
} else {
int n = p.size();
if (i == 0) {
append(p, big);
append(p, big);
} else if (i == 1) {
append(p, big);
append(p, big);
append(p, small);
} else if (i == 2) {
append(p, big);
append(p, small);
append(p, big);
} else if (i == 3) {
int p0 = -1, p1 = -1;
for (int j = 0; j < n; j++) if (p[j] == 0) {
p0 = j;
break;
}
for (int j = 0; j < n; j++) if (p[j] == 1) {
p1 = j;
break;
}
bool ok = (p0 != -1 && p1 != -1 && p1 < p0);
if (ok) {
append(p, big);
append(p, big);
append(p, 1);
} else {
append(p, big);
append(p, small);
append(p, big);
append(p, small);
}
}
}
}
return p;
}
