#include <bits/stdc++.h>
using namespace std;
#include "perm.h"
#ifdef LOCAL
#include "grader.cpp"
#endif
#define ll long long
vector<int> construct_permutation(long long k){
vector<int> p;
int base=4;
vector<int> conv;
ll temp=k;
while(temp>0){
conv.push_back(temp%base);
temp/=base;
}
reverse(conv.begin(),conv.end());
for(int i=0;i<conv.size();i++){
temp=conv[i];
if(!i){
temp=conv[i]-1;
}
else{
p.push_back(p.size());
p.push_back(p.size());
}
while(temp>0){
if(p.empty()){
temp--;
p.push_back(0);
continue;
}
if(temp==1){
p.insert(p.begin(),p.size());
temp--;
continue;
}
ll DP[p.size()];
for(int i=0;i<p.size();i++){
DP[i]=1;
for(int j=0;j<i;j++){
if(p[j]<p[i]){
DP[i]+=DP[j];
}
}
}
DP[0]++;
for(int i=1;i<p.size();i++){
DP[i]+=DP[i-1];
}
for(int i=p.size()-1;i>=0;i--){
if(DP[i]<=temp){
temp-=DP[i];
p.insert(p.begin()+i+1,p.size());
break;
}
}
}
}
return p;
}
