#include <vector>
#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
void add(int n, string pre, string suf){
if(n==1){
return;
}
string s="",tmp="";
for(int i=0;i<n;i++){
s+='0';
}
for(int i=0;i<n/2;i++){
s[i]='1';
add_element(pre+s+suf);
s[i]='0';
}
for(int i=0;i<n/2;i++){
tmp+='1';
}
add(n/2,pre+tmp,suf);
add(n/2,pre,tmp+suf);
}
vector<int> solve(int n, string cur, int l, int r, vector<int> pos){
if(r==l){
return {pos[0]};
}
vector<int> l_pos,r_pos;
string l_cur=cur,r_cur=cur;
for(int i=0;i<n;i++){
cur[pos[i]]='1';
if(check_element(cur)){
l_cur[pos[i]]='1';
l_pos.push_back(pos[i]);
}else{
r_cur[pos[i]]='1';
r_pos.push_back(pos[i]);
}
cur[pos[i]]='0';
}
vector<int> ans1=solve(n/2,r_cur,l,r-n/2,l_pos),ans2=solve(n/2,l_cur,l+n/2,r,r_pos);
for(auto u:ans2){
ans1.push_back(u);
}
return ans1;
}
std::vector<int> restore_permutation(int n, int w, int r) {
int cnt;
string s="",tmp;
vector<int> ans,real(n);
for(int i=0;i<n;i++){
s+='0';
ans.push_back(i);
}
add(n,"","");
compile_set();
ans=solve(n,s,0,n-1,ans);
for(int i=0;i<n;i++){
real[ans[i]]=i;
}
return real;
}
