#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void recalculate_permutation(vector<int> &p)
{
map<int, int> mp;
int t=0;
for (auto x:p) mp[x]=0;
for (auto &[x, y]:mp) y=t++;
for (int i=0; i<p.size(); i++) p[i]=mp[p[i]];
}
std::vector<int> construct_permutation(long long k)
{
vector<int> b, res;
while (k) b.push_back(k&3), k/=4;
if (b.back()==1);
if (b.back()==2) res.push_back(0);
if (b.back()==3) res.push_back(1), res.push_back(0);
for (int i=(int)b.size()-2; i>=0; i--)
{
int x=b[i];
if (x==0) res.push_back(1e9), res.push_back(1e9+1);
else if (x==1) res.push_back(1e9), res.push_back(1e9+1), res.push_back(-1);
else if (x==2) res.push_back(1e9), res.push_back(-1), res.push_back(1e9+1);
else
{
int p0, p1;
for (int j=0; j<res.size(); j++)
{
if (res[j]==0) p0=j;
if (res[j]==1) p1=j;
}
if (p1<p0)
{
for (int j=0; j<res.size(); j++) if (res[j]<=1) res[j]--;
res.push_back(1e9);
res.push_back(1e9+1);
res.push_back(1);
}
else
{
res.push_back(1e9);
res.push_back(-1);
res.push_back(1e9+1);
res.push_back(-2);
}
}
recalculate_permutation(res);
}
return res;
}
