#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> construct_permutation(ll k) {
vector<ll> pw(38);
pw[0] = 1;
for (int i = 1; i < 38; i++) {
pw[i] = pw[i - 1] * 3;
}
int p = -1, cnt = 0;
for (int i = 0; i < 38; i++) {
if (k / pw[i] % 3) {
p = i;
cnt++;
}
}
int v = cnt - 1;
int u = v;
vector<int> ans;
if (k / pw[p] % 3 == 2) {
ans.push_back(u++);
}
for (int i = p - 1; i >= 0; i--) {
if (k / pw[i] % 3 == 0) {
ans.push_back(u + 1);
ans.push_back(u);
u += 2;
} else if (k / pw[i] % 3 == 1) {
ans.push_back(u + 1);
ans.push_back(u);
ans.push_back(--v);
u += 2;
} else {
ans.push_back(u + 1);
ans.push_back(--v);
ans.push_back(u);
u += 2;
}
}
return ans;
}
