#include <vector>
#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
vector<int> ans;
string bit;
void generate(int l, int r){
if(r - l == 1) return;
int m = (l + r) >> 1;
for(int i = l; i < m; i++){
bit[i] = '1';
add_element(bit);
bit[i] = '0';
}
for(int i = m; i < r; i++) bit[i] = '1';
generate(l, m);
for(int i = m; i < r; i++) bit[i] = '0';
for(int i = l; i < m; i++) bit[i] = '1';
generate(m, r);
for(int i = l; i < m; i++) bit[i] = '0';
}
void query(int l, int r, vector<int> idx){
if(r - l == 1){
ans[idx[0]] = l;
return;
}
vector<int> lf, rg;
for(auto &k : idx){
bit[k] = '1';
//1 to left, 0 to right
if(check_element(bit)) lf.emplace_back(k);
else rg.emplace_back(k);
bit[k] = '0';
}
assert(lf.size() == rg.size());
int m = (l + r) >> 1;
for(auto &k : rg) bit[k] = '1';
query(l, m, lf);
for(auto &k : rg) bit[k] = '0';
for(auto &k : lf) bit[k] = '1';
query(m, r, rg);
for(auto &k : lf) bit[k] = '0';
}
vector<int> restore_permutation(int n, int w, int r) {
ans.resize(n);
vector<int> idx(n);
for(int i = 0; i < n; i++) bit += '0';
iota(idx.begin(), idx.end(), 0);
//[0, n)
generate(0, n);
compile_set();
query(0, n, idx);
return ans;
}
