#include <bits/stdc++.h>
#include "messy.h"
#include <vector>
using namespace std;
vector<int> restore_permutation(int n, int w, int r) {
vector <int> p (n);
auto pre = [&] (int l, int r, auto &&pre) {
if (l >= r) return;
int mid = (l + r) / 2;
string s(n, '0');
for (int i = l; i <= r; i++){
s[i] = '1';
}
for (int i = l; i <= mid; i++){
s[i] = '0';
add_element(s);
s[i] = '1';
}
pre(l, mid, pre);
pre(mid + 1, r, pre);
};
pre(0, n - 1, pre);
compile_set();
auto solve = [&] (int l, int r, vector <int> ps, auto &&solve) {
if (ps.size() == 1) return;
int mid = (l + r) / 2;
string s(n, '0');
vector <int> a,b;
for (int i: ps) s[i] = '1';
for (int i: ps) {
s[i] = '0';
if (check_element(s)) a.push_back(i);
else b.push_back(i), p[i]+=ps.size() / 2;
s[i] = '1';
}
solve(l, mid, a, solve);
solve(mid + 1, r, b, solve);
};
vector <int> v;
for (int i = 0; i < n; i++) v.push_back(i);
solve(0, n-1, v, solve);
return p;
}
