#include <vector>
#include<bits/stdc++.h>
#include "messy.h"
using namespace std;
vector<int>ans;
int N;
void add(int st,int en,int l,int r){
if(st==en)return;
int m=(st+en)/2;
string pre,suf,mid;
for(int i=l;i<st;i++)pre=pre+'1';
for(int i=en+1;i<=r;i++)suf=suf+'1';
for(int i=st;i<=m;i++){
mid="";
for(int j=st;j<=en;j++){
if(j==i)mid=mid+'1';
else mid=mid+'0';
}
//cout<<pre+mid+suf<<"\n";
add_element(pre+mid+suf);
}
add(st,m,l,r);
add(m+1,en,l,r);
}
void check(int st,int en,int l,int r,vector<int>pre,vector<int>mid,vector<int>suf){
//cerr<<st<<' '<<en<<"\n";
//cerr<<ans.size()<<' '<<mid.size()<<"\n";
if(st==en)return void(ans[mid[0]]=st-1);
string s(N,'0');
int m=(st+en)/2;
for(auto x:pre)s[x]='1';
for(auto x:suf)s[x]='1';
vector<int> npre=pre,nsuf=suf,midl,midr;
for(auto x:mid){
s[x]='1';
//cerr<<s<<"\n";
if(check_element(s))midl.push_back(x),npre.push_back(x);
else midr.push_back(x),nsuf.push_back(x);
s[x]='0';
}
check(st,m,l,r,pre,midl,nsuf);
check(m+1,en,l,r,npre,midr,suf);
}
std::vector<int> restore_permutation(int n, int w, int r) {
//cerr<<"work\n";
ans.clear();
N=n;
add(1,n,1,n);
//cerr<<"add work\n";
compile_set();
ans.resize(n);
vector<int>mid;
for(int i=0;i<n;i++)mid.push_back(i);
//cerr<<"work\n";
check(1,n,1,n,vector<int>(),mid,vector<int>());
//cerr<<"check work\n";
return ans;
}
