#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
vector<int> p;
void add(int l, int r, string s) {
if(l == r) 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';
add(mid+1, r, s);
for(int i=l; i<=mid; i++) s[i] = '0';
for(int i=mid+1; i<=r; i++) s[i] = '1';
add(l, mid, s);
}
void query(int l, int r, string s) {
if(l == r) {
for(int i=0; i<s.size(); i++) {
if(s[i] == '0') p[i] = l;
}
return;
}
int mid = (l+r)/2;
vector<int> f, nf;
for(int i=0; i<s.size(); i++) {
if(s[i] == '1') continue;
s[i] = '1';
if(check_element(s)) f.push_back(i);
else nf.push_back(i);
s[i] = '0';
}
for(auto i: f) s[i] = '1';
query(mid+1, r, s);
for(auto i: f) s[i] = '0';
for(auto i: nf) s[i] = '1';
query(l, mid, s);
}
std::vector<int> restore_permutation(int n, int w, int r) {
string s;
s.assign(n, '0');
p.assign(n, 0);
add(0, n-1, s);
compile_set();
query(0, n-1, s);
return p;
}
