#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int BASE = 3;
vector<int> ans[] = {
{},
{},
{0}, // 2
{1, 0}, // 3
{0, 1}, // 4
{1, 2, 0}, // 5
{0, 2, 1} // 6
};
std::vector<int> construct_permutation(long long k)
{
if (k <= BASE) return ans[k];
else if (k % BASE == 0) {
vector<int> res = construct_permutation(k/BASE);
auto a = ans[BASE];
for (auto &x: res) x += a.size();
res.insert(res.begin(), a.begin(), a.end());
return res;
} else {
long long rem = k%BASE;
vector<int> res = construct_permutation(k - rem);
auto a = ans[rem + 1];
for (auto &x: a) x += res.size();
res.insert(res.begin(), a.begin(), a.end());
return res;
}
}
