#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
ostream& operator<<(ostream &out, string str) {
for(char c : str) out << c;
return out;
}
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
return out << "(" << p.ST << ", " << p.ND << ")";
}
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
out << "{";
for(auto it = a.begin(); it != a.end(); it = next(it))
out << (it != a.begin() ? ", " : "") << *it;
return out << "}";
}
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
cerr << a << ", ";
dump(x...);
}
#ifdef DEBUG
# define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
# define debug(...) false
#endif
template<class T> int size(T && a) { return (int) a.size(); }
using LL = long long;
using PII = pair<int, int>;
#include "messy.h"
vector<int> restore_permutation(int n, int w, int r) {
function<void(int, int)> add = [&](int l, int r) {
if(l == r) return;
int m = (l + r) / 2;
string b(n, '0');
REP(i, n) if(i < l || r < i)
b[i] = '1';
FOR(i, l, (l + r) / 2) {
b[i] = '1';
add_element(b);
b[i] = '0';
}
add(l, m), add(m + 1, r);
};
add(0, n - 1);
compile_set();
vector<int> ans(n);
REP(i, n) ans[i] = i;
auto solve = [&](auto self, int l, int r, vector<int> opt) {
if(l == r) {
ans[l] = opt[0];
return;
}
string b(n, '1');
for(int i : opt) b[i] = '0';
vector<int> x, y;
for(int i : opt) {
b[i] = '1';
if(check_element(b))
x.emplace_back(i);
else
y.emplace_back(i);
b[i] = '0';
}
int m = (l + r) / 2;
self(self, l, m, x), self(self, m + 1, r, y);
};
solve(solve, 0, n - 1, ans);
vector<int> p(n);
REP(i, n) p[ans[i]] = i;
return p;
}
