#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "messy.h"
#else
void add_element(string s) {}
void compile_set() {}
bool check_element(string s) { return 0; }
#endif
string O(int n) {
string s = "";
for(int i = 0; i < n; ++i) {
s += '0';
}
return s;
}
string s;
vector<int> dr, rd;
inline int M(int l, int r) {
return (l + r) / 2;
}
void A(int l, int r) {
if(r - l <= 2) return;
int m = M(l, r);
for(int i = l; i < m; ++i) s[i] = '1';
for(int i = m; i < M(m, r); ++i) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
for(int i = l; i < m; ++i) s[i] = '0';
///
for(int i = m; i < r; ++i) s[i] = '1';
for(int i = l; i < M(l, m); ++i) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
for(int i = m; i < r; ++i) s[i] = '0';
A(l, m);
A(m, r);
}
void C(int l, int r) {
if(r - l <= 2) return;
int m = M(l, r), x = m;
for(int i = l; i < m; ++i) s[rd[i]] = '1';
for(int i = m; i < r; ++i) {
s[rd[i]] = '1';
if(check_element(s)) {
swap(dr[rd[i]], dr[rd[x]]);
swap(rd[i], rd[x]); ++x;
}
s[rd[i]] = '0';
}
for(int i = l; i < m; ++i) s[rd[i]] = '0';
x = l;
for(int i = m; i < r; ++i) s[rd[i]] = '1';
for(int i = l; i < m; ++i) {
s[rd[i]] = '1';
if(check_element(s)) {
swap(dr[rd[i]], dr[rd[x]]);
swap(rd[i], rd[x]); ++x;
}
s[rd[i]] = '0';
}
for(int i = m; i < r; ++i) s[rd[i]] = '0';
C(l, m);
C(m, r);
}
vector<int> restore_permutation(int n, int = 0, int = 0) {
dr.resize(n);
s = O(n);
rd.resize(n);
for(int i = 0; i < M(0, n); ++i) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
A(0, n);
compile_set();
int x = 0, y = M(0, n);
for(int i = 0; i < n; ++i) {
s[i] = '1';
if(check_element(s)) {
rd[x] = i;
dr[i] = x++;
} else {
rd[y] = i;
dr[i] = y++;
}
s[i] = '0';
}
return dr;
}
#ifdef wambule
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
return 0;
}
#endif
