#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
string s;
vector <int> p,v,res;
string add(string s, int l, int r){
for (int i=l;i<=r;i++)
s[i]='1';
return s;
}
void dnc(int l, int r, string s){
if (l==r)
return;
int mid=(l+r)>>1;
for (int i=l;i<=mid;i++){
s[i]='1';
add_element(s);
s[i]='0';
}
dnc(l,mid,add(s,mid+1,r));
dnc(mid+1,r,add(s,l,mid));
}
string add(string s, vector <int> v){
for (int i:v)
s[i]='1';
return s;
}
void dnc2(int l, int r, vector <int> v, string s){
if (l==r){
p.push_back(v[0]);
return;
}
vector <int> L,R;
for (int i:v){
s[i]='1';
if (check_element(s))
L.push_back(i);
else
R.push_back(i);
s[i]='0';
}
int mid=(l+r)>>1;
dnc2(l,mid,L,add(s,R));
dnc2(mid+1,r,R,add(s,L));
}
vector <int> restore_permutation(int n, int w, int r){
for (int i=0;i<n;i++){
s+='0';
v.push_back(i);
}
dnc(0,n-1,s);
compile_set();
dnc2(0,n-1,v,s);
res.resize(n);
for (int i=0;i<n;i++)
res[p[i]]=i;
return res;
}
