#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
vi res;
int N;
string submit;
void firstHalf(int l,int r){
if(r-l){
int m = (l+r)/2;
for(int i=0;i<N;i++){
if(i < l || i > r){
submit[i] = '1';
}
}
for(int i=l;i<=m;i++){
submit[i] = '1';
add_element(submit);
submit[i] = '0';
}
for(int i=0;i<N;i++){
if(i < l || i > r){
submit[i] = '0';
}
}
firstHalf(l,m);
firstHalf(m+1,r);
}
}
void secondHalf(int l,int r,vi used,vi unused){
if(r-l){
int m = (l+r)/2;
for(int it : unused){
submit[it] = '1';
}
vi left,right;
for(int it : used){
submit[it] = '1';
bool valid = check_element(submit);
if(valid){
left.emplace_back(it);
}else{
right.emplace_back(it);
}
submit[it] = '0';
}
for(int i=0;i<N;i++){
submit[i] = '0';
}
vi lunused = unused, runused = unused;
lunused.insert(lunused.begin(),left.begin(),left.end());
runused.insert(runused.begin(),right.begin(),right.end());
secondHalf(l,m,left,runused);
secondHalf(m+1,r,right,lunused);
}else{
res[used.back()] = l;
}
}
std::vector<int> restore_permutation(int n, int w, int r) {
N = n;
vi used,unused;
for(int i=0;i<N;i++){
res.emplace_back(i);
submit.push_back('0');
used.emplace_back(i);
}
firstHalf(0,N-1);
compile_set();
secondHalf(0,N-1,used,unused);
return res;
}
