#include <bits/stdc++.h>
#define eb emplace_back
#include "messy.h"
using namespace std;
void write(int n,int l,int r,int f){
string s(n,'0');
if(l==0&&r==n){
for(int i=0;i<n/2;i++){
s[i]='1';
add_element(s);
s[i]='0';
}
write(n,0,n/2,1);
write(n,n/2,n,0);
return;
}
if(r-l==1)return;
if(f){
for(int i=r;i<r+r-l;i++){
s[i]='1';
}
}else{
for(int i=l-(r-l);i<l;i++){
s[i]='1';
}
}
int m=(l+r)/2;
for(int i=l;i<m;i++){
s[i]='1';
add_element(s);
s[i]='0';
}
write(n,l,m,1);
write(n,m,r,0);
}
std::vector<int> restore_permutation(int n, int w, int r) {
write(n,0,n,1);
compile_set();
vector<vector<int>> vs(2*n);
string s(n,'0');
for(int i=0;i<n;i++){
s[i]='1';
if(check_element(s)){
vs[2].eb(i);
}else{
vs[3].eb(i);
}
s[i]='0';
}
for(int i=2;i<n;i++){
int p=((i>>1)<<1);
if((i&1)==0){
p|=1;
}
s=string(n,'0');
for(auto &e:vs[p]){
s[e]='1';
}
for(auto &e:vs[i]){
s[e]='1';
if(check_element(s)){
vs[i<<1].eb(e);
}else{
vs[i<<1|1].eb(e);
}
s[e]='0';
}
}
vector<int> p(n);
for(int i=0;i<n;i++){
p[vs[i+n][0]]=i;
}
return p;
}
