#include <bits/stdc++.h>
#include "perm.h"
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#define endl '\n'
#define ll long long
#define pb push_back
#define vi vector<int>
#define vll vector<long long>
#define sz(x) (int)x.size()
#define int long long
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define piii pair<int,pii>
#define rep(i,a,b) for (ll i = a; i<b; i++)
#define repo(i,a,b) for (int i = a; i>=b; i--)
#define sets(a,b) memset(a, b, sizeof(a))
#define fi first
#define se second
int dy[8] = {0, 0, 1, -1, 1, -1 , 1, -1};
int dx[8] = {1, -1, 0, 0, 1, -1, -1, 1};
//int dp[100001][100001];
//int arr[100001];
const int MOD = 1e9+7;
const int INF = 1e9;
const int LOG = 20;
const int maxn = 1e5 + 5;
vector<signed> construct_permutation(int k){
vector<double> ans;
int bit = 64-__builtin_clzll(k);
bool flag = false;
while(bit > 0){
bit -= 2;
if(bit == -1){
ans.pb(1e9);
if(k&1){ans.pb(-1e9);}
}else{
int val = (k>>bit)&3;
if(ans.empty()){
if(val==2)ans = {0};
else{ans = {1,0}; flag = true;}
}else{
if(val == 0){
ans.pb(1e9);
ans.pb(1e9+1);
}
else if(val == 1){
ans.pb(1e9);
ans.pb(-1e9);
ans.pb(1e9+1);
}
else if(val == 2){
ans.pb(1e9);
ans.pb(-1e9);
ans.pb(1e9+1);
ans.pb(-1e9-1);
flag = true;
}else{
if(!flag){
ans.pb(1e9);
ans.pb(-1e9);
ans.pb(1e9+1);
ans.pb(-1e9-1);
flag = true;
}
else{
ans.pb(1e9);
ans.pb(1e9+1);
ans.pb(1.5);
}
}
}
}
vector<double> uni(all(ans));
sort(all(uni));
for(auto &it : ans){
it = lower_bound(all(uni),it)-uni.begin();
}
}
return vector<signed>(all(ans));
}
