#include <vector>
#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
vector<int> ans;
void dnc1(int l,int r){
if(l==r)return;
string s;
for(int i=0;i<n;i++){
if(i<l||i>r)s+='1';
else s+='0';
}
int m=(l+r)/2;
for(int x=l;x<=m;x++){
s[x]='1';
add_element(s);
s[x]='0';
}
dnc1(l,m);
dnc1(m+1,r);
}
void dnc2(vector<int> v,int l,int r){
if(l==r){
ans[v[0]]=l;
return;
}
string s;
for(int i=0;i<n;i++)s+='1';
for(int x:v)s[x]='0';
int m=(l+r)/2;
vector<int> v1,v2;
for(int x:v){
s[x]='1';
if(check_element(s)){
v1.push_back(x);
}
s[x]='0';
}
for(int i:v){
bool b=0;
for(int j:v1)b|=i==j;
if(!b)v2.push_back(i);
}
dnc2(v1,l,m);
dnc2(v2,m+1,r);
}
std::vector<int> restore_permutation(int N, int w, int r) {
n=N;
ans.resize(n);
dnc1(0,n-1);
compile_set();
vector<int> v(n);
iota(begin(v),end(v),0);
dnc2(v,0,n-1);
return ans;
}
