#include <vector>
#include <string>
#include "messy.h"
using namespace std;
string tmp;
void add(int l,int r) {
int m=(l+r)>>1;
for (int i=l;i<m;i++) {
tmp[i]='1';
add_element(tmp);
tmp[i]='0';
}
if (l+2==r) return;
for (int i=m;i<r;i++) tmp[i]='1';
add(l,m);
for (int i=l;i<m;i++) tmp[i]='1';
for (int i=m;i<r;i++) tmp[i]='0';
add(m,r);
for (int i=l;i<r;i++) tmp[i]='0';
}
vector<int> ans;
void solve(int l,int r,const vector<int> &candid,const vector<int> &pre) {
if (l+1==r) {
ans[candid.front()]=l;
return;
}
for (auto i:pre) {
tmp[i]='1';
}
vector<int> ll;
vector<int> rr;
for (auto i:candid) {
tmp[i]='1';
if (check_element(tmp)) {
ll.push_back(i);
} else {
rr.push_back(i);
}
tmp[i]='0';
}
int m=(l+r)>>1;
solve(l,m,ll,rr);
solve(m,r,rr,ll);
for (auto i:pre) {
tmp[i]='0';
}
}
std::vector<int> restore_permutation(int n, int w, int r) {
for (int i=0;i<n;i++) {
tmp.push_back('0');
}
add(0,n);
compile_set();
ans.resize(n);
for (int i=0;i<n;i++) {
tmp[i]='0';
}
vector<int> init(n);
for (int i=0;i<n;i++) {
init[i]=i;
}
solve(0,n,init,vector<int>());
return ans;
}
