#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e9;
vector < int > construct_permutation(ll k){
ll bit = 0, was = 0;
for(ll i = 0; i < 60; i++)
if(k >= (1ll << i))
bit = i + 1;
vector < double > ans;
map < double, int > val;
while(bit > 0){
bit -= 2;
if(bit == -1){
ans.push_back(inf);
if(k & 1) ans.push_back(-inf);
continue;
}
ll v = (k >> bit) & 3;
if(ans.empty()){
if(v == 2) ans = {0};
else ans = {1, 0}, was = 1;
continue;
}
if(v == 0) ans.push_back(inf), ans.push_back(inf + 1);
else if(v == 1) ans.push_back(inf), ans.push_back(inf + 1), ans.push_back(-inf), was = 1;
else if(v == 2) ans.push_back(inf), ans.push_back(-inf), ans.push_back(inf + 1), was = 1;
else if(!was) ans.push_back(inf), ans.push_back(-inf), ans.push_back(inf + 1), ans.push_back(-inf - 1), was = 1;
else ans.push_back(inf), ans.push_back(inf + 1), ans.push_back(1.5);
vector < double > c = ans;
sort(c.begin(), c.end());
for(ll i = 0; i < c.size(); i++) val[c[i]] = i;
for(ll i = 0; i < ans.size(); i++) ans[i] = val[ans[i]];
}
vector < double > c = ans;
sort(c.begin(), c.end());
for(ll i = 0; i < c.size(); i++) val[c[i]] = i;
for(ll i = 0; i < ans.size(); i++) ans[i] = val[ans[i]];
vector < int > res;
for(auto &i : ans) res.push_back(i);
return res;
}
