#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
int n;
void build(int l, int r){
int k = (l+r)/2;
string cur;
cur.resize(n, '1');
for(int i = l; i <= r; i++){
cur[i] = '0';
}
for(int i = l; i <= k; i++){
cur[i] = '1';
add_element(cur);
cur[i] = '0';
}
if(l+1 >= r) return;
build(l, k);
build(k+1, r);
}
vector<int> p;
void filt(int l, int r, vector<int> cdds, string tmpl){
if(l == r){
p[cdds[0]] = l;
return;
}
int m = (l+r)/2;
vector<int> lcdds, rcdds;
string ltmpl = tmpl;
string rtmpl = tmpl;
for(int i : cdds){
string cur = tmpl;
cur[i] = '1';
bool found = check_element(cur);
if(found){
ltmpl[i] = '1';
lcdds.push_back(i);
}else{
rtmpl[i] = '1';
rcdds.push_back(i);
}
}
filt(l, m, lcdds, rtmpl);
filt(m+1, r, rcdds, ltmpl);
}
vector<int> restore_permutation(int n, int w, int r){
::n = n;
build(0, n-1);
compile_set();
vector<int> cdds;
for(int i = 0; i < n; i++){
cdds.push_back(i);
p.push_back(i);
}
string tmpl;
tmpl.resize(n, '0');
filt(0, n-1, cdds, tmpl);
return p;
}
