#include "bits/stdc++.h"
#include "messy.h"
using namespace std;
#define f1(n) for(int i=0;i<n;i++)
#define f3(n) for(int j=0;j<n;j++)
#define f2(m,n,q) for(int i=m;i<n;i+=q)
#define f4(m,n,q) for(int j=m;j<n;j+=q)
#define pb push_back
using pr=pair<int,int>;
using ar=array<int,3>;
vector<int>p;
void print(int l,int r,string& s) {
//base case
if (r-l==1)return;
int mid=(l+r)/2;
for (int i=l;i<mid;i++) {
s[i]='1';
add_element(s);
s[i]='0';
}
for (int i=l;i<mid;i++) {
s[i]='1';
}
print(mid,r,s);
for (int i=l;i<r;i++) {
if (i<mid)s[i]='0';
else s[i]='1';
}
print(l,mid,s);
}
void query(int l,int r,string& s,vector<int>v) {
// base_case
if (r-l==1) {
p[v[0]]=l;
return;
}
int mid=(l+r)/2;
vector<int> vl,vr;
for (auto it:v) {
s[it]='1';
if (check_element(s))vl.pb(it);
else vr.pb(it);
s[it]='0';
}
for (auto it:vr)s[it]='1';
query(l,mid,s,vl);
for (auto it:vr)s[it]='0';
for (auto it:vl)s[it]='1';
query(mid,r,s,vr);
for (auto it:vl)s[it]='0';
}
vector<int> restore_permutation(int n, int w, int r) {
string s(n,'0');
print(0,n,s);
vector<int>v;
for (int i=0;i<n;i++)v.pb(i);
p.resize(n);
query(0,n,s,v);
return p;
}
