#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
void add_seg(int n, int l, int r) {
if (l + 1 == r)
return;
string s(n, '1');
fill(s.begin() + l, s.begin() + r, '0');
int m = (r + l) / 2;
for (int i = l; i < m; i++) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
add_seg(n, l, m);
add_seg(n, m, r);
}
vector<int> ans;
void solve(int n, int l, int r, vector<int> t) {
if (l + 1 == r) {
ans[t[0]] = l;
return;
}
int m = (r + l) / 2;
string s(n, '1');
for (int x : t)
s[x] = '0';
vector<int> lh, rh;
for (int x : t) {
s[x] = '1';
if (check_element(s)) {
lh.push_back(x);
} else {
rh.push_back(x);
}
s[x] = '0';
}
assert(lh.size() == rh.size());
solve(n, l, m, lh);
solve(n, m, r, rh);
}
std::vector<int> restore_permutation(int n, int w, int r) {
add_seg(n, 0, n);
compile_set();
ans.resize(n);
vector<int> v(n);
iota(v.begin(), v.end(), 0);
solve(n, 0, n, v);
return ans;
}
