#include <bits/stdc++.h>
#define f(i,j,n) for(ll i = j; i < n; ++i)
#define fr(i,j,n) for(ll i = j; i >= n; --i)
#define sz(v) (ll) v.size()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
const int N = 4e3 + 20;
const ll mod = 1e9 + 7;
vi construct_permutation(ll k){
ll aux = k, cn = 0;
vll in[5];
ll np[5];
in[1] = {}, in[2] = {0}, in[3] = {1,0};
np[1] = -1, np[2] = 0, np[3] = 1;
while(aux >= 4) aux >>= 2, cn++;
vll ans = in[aux];
ll na = np[aux];
fr(i,cn,1){
ll j = (k>>(2*(i-1)))%4;
if(j == 0){
ans.push_back(++na);
ans.push_back(++na);
}
if(j == 1){
ans.push_back(++na);
ans.push_back(++na);
for(auto &it : ans) it++;
ans.push_back(0);
na++;
}
if(j == 2){
ans.push_back(++na);
for(auto &it : ans) it++;
ans.push_back(0);
na++;
ans.push_back(++na);
}
if(j == 3){
ll p[2];
f(ji,0,sz(ans)) if(ans[ji] < 2) p[ans[ji]] = ji;
if(p[1] < p[0]){
ans.push_back(++na);
ans.push_back(++na);
for(auto &it : ans) if(it >= 2) it++;
ans.push_back(2);
na++;
}
else{
ans.push_back(++na);
for(auto &it : ans) it++;
ans.push_back(0);
na++;
ans.push_back(++na);
for(auto &it : ans) it++;
ans.push_back(0);
na++;
}
}
}
vi ai;
for(auto it : ans) ai.push_back((int) it);
return ai;
}
// int main(){
// int k; cin >> k;
// vector<int> nm = construct_permutation(k);
// for(auto it : nm) cout << it << " ";
// cout << endl;
// return 0;
// }
