#include "messy.h"
#include <bits/stdc++.h>
int n;
std::string s;
std::vector<int> p;
void dc(int l, int r) {
if (l == r) {
return;
}
int md = (l + r) / 2;
s = std::string(n, '1');
for (int i = l; i <= r; ++i) {
s[i] = '0';
}
for (int i = l; i <= md; ++i) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
dc(l, md);
dc(md + 1, r);
}
void qry(int l, int r, std::vector<int> cands) {
if (l == r) {
p[cands[0]] = l;
return;
}
int md = (l + r) / 2;
s = std::string(n, '1');
for (auto p : cands) {
s[p] = '0';
}
std::vector<int> lt, rt;
for (auto p : cands) {
s[p] = '1';
(check_element(s) ? lt : rt).push_back(p);
s[p] = '0';
}
qry(l, md, lt);
qry(md + 1, r, rt);
}
std::vector<int> restore_permutation(int n, int w, int r) {
::n = n;
dc(0, n - 1);
compile_set();
std::vector<int> cands(n); iota(cands.begin(), cands.end(), 0);
p = std::vector<int>(n);
qry(0, n - 1, cands);
return p;
}
