#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
const int N = 2e5 + 5;
vector <int> construct_permutation(ll k) {
string s;
ll oo = k;
while (oo > 0) {
s += char ((oo % 4) + 48);
oo /= 4;
}
reverse(s.begin(), s.end());
vector <double> ret;
bool ok = 0;
int mn = 0, mx = 0;
if (s[0] == '2') {
ret.pb (0);
}
else if (s[0] == '3') {
ret.pb (1);
ret.pb (0);
ok = 1;
mx = 1;
}
for (int i = 1; i < (int)s.sz; ++i) {
if (s[i] == '0' or s[i] == '1') {
ret.pb (mx + 1);
ret.pb (mx + 2);
if (s[i] == '1') {
ret.pb (mn - 1);
mn--;
}
mx += 2;
}
else if (s[i] == '2') {
ret.pb (mx + 1);
ret.pb (mn - 1);
ret.pb (mx + 2);
mn--;
mx += 2;
}
else {
if (ok) {
ret.pb (mx + 1);
ret.pb (mx + 2);
ret.pb ((mn + 1) + 0.5);
}
else {
ret.pb (mx + 1);
ret.pb (mn - 1);
ret.pb (mx + 2);
ret.pb (mn - 2);
ok = 1;
mn -= 2;
}
mx += 2;
}
}
map <double, int> m;
for (double i : ret) {
m[i]++;
}
int sum = 0;
for (auto i : m) {
m[i.ff] = sum + i.ss - 1;
sum += i.ss;
}
vector <int> jog;
for (double i : ret) {
jog.pb (m[i]);
m[i]--;
}
return jog;
}
//int main () {
// freopen ("input.txt", "r", stdin);
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// int q;
// cin >> q;
// while ( q-- ) {
// ll k;
// cin >> k;
// vector <int> kk = construct_permutation(k);
// for (int i : kk) {
// cout << i << " ";
// }
// cout << "\n";
// }
//}
