#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
string s;
void gen(int l, int r) {
if(l+1 == r) {
return;
}
int mid = (r+l)>>1;
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';
}
gen(mid, r);
for(int i = l; i < mid; i++) {
s[i] = '0';
}
for(int i = mid; i < r; i++) {
s[i] = '1';
}
gen(l, mid);
for(int i = mid; i < r; i++) {
s[i] = '0';
}
}
vector<int> ans;
void get(int l, int r, vector<int> indices) {
if(l+1 == r) {
ans[indices[0]] = l;
return;
}
int mid = (l+r)>>1;
vector<int> a, b;
for(auto i : indices) {
s[i] = '1';
if(check_element(s))
a.push_back(i);
else
b.push_back(i);
s[i] = '0';
}
for(auto i : a) {
s[i] = '1';
}
get(mid, r, b);
for(auto i : a) {
s[i] = '0';
}
for(auto i : b) {
s[i] = '1';
}
get(l, mid, a);
for(auto i : b) {
s[i] = '0';
}
}
std::vector<int> restore_permutation(int n, int w, int r) {
s = string(n, '0');
gen(0, n);
compile_set();
ans = vector<int>(n, -1);
vector<int> ind;
for(int i = 0; i < n; i++) ind.push_back(i);
get(0, n, ind);
return ans;
}
