#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
string curquery;
int n;
void genQueries(int s, int e){
if (s==e){
return;
}
int m = (s+e)/2;
for (int i = s; i<=m; i++){
curquery[i]='1';
//cout<<curquery<<'\n';
add_element(curquery);
curquery[i]='0';
}
for (int i = m+1; i<=e; i++){
curquery[i]='1';
}
genQueries(s,m);
for (int i = s; i<=m; i++){
curquery[i]='1';
}
for (int i = m+1; i<=e; i++){
curquery[i]='0';
}
genQueries(m+1,e);
}
vector<int> permutation;
vector<bool> active;
void genResult(int s, int e){
if (s==e){
for (int i = 0; i<n; i++){
if (active[i]){
permutation[s]=i;
return;
}
}
assert(1==0);
return;
}
int m = (s+e)/2;
vector<int> touse;
for (int i = 0; i<n; i++){
if (active[i]){
curquery[i]='0';
touse.push_back(i);
} else {
curquery[i]='1';
}
}
vector<int> l;
vector<int> r;
for (int t : touse){
curquery[t]='1';
//cout<<curquery<<'\n';
if (check_element(curquery)){
//cout<<"l\n";
l.push_back(t);
} else {
//cout<<"r\n";
r.push_back(t);
}
curquery[t]='0';
}
/*cout<<"checking "<<s<<' '<<e<<'\n';
cout<<"l: ";
for (int i : l){
cout<<i<<' ';
}cout<<'\n';
cout<<"r: ";
for (int i : r){
cout<<i<<' ';
}cout<<'\n';*/
for (int i : l){
active[i]=true;
}
for (int i : r){
active[i]=false;
}
genResult(s,m);
for (int i : l){
active[i]=false;
}
for (int i : r){
active[i]=true;
}
genResult(m+1,e);
}
std::vector<int> restore_permutation(int N, int w, int r) {
n = N;
curquery.resize(n,'0');
genQueries(0,n-1);
compile_set();
permutation.resize(n);
active.resize(n,true);
genResult(0,n-1);
vector<int> ans(n);
for (int i = 0; i<n; i++){
ans[permutation[i]]=i;
}
return ans;
}
