#include <vector>
#include "messy.h"
#include <string>
#include <iostream>
#include <bitset>
using namespace std;
int const N = 128;
vector<int> ans;
void find(int n,int l,int r,bitset<N> bs){
//cout << bs << endl;
bitset<N> newbs;
string temp;
for(int i{};i < n;i++) temp += '0'+(!bs[i]);
int md = l+(r-l)/2;
for(int i{};i < n;i++){
if(bs[i]){
temp[i] = '1';
if(check_element(temp)){
if(l == md){
ans[l-1] = i;
for(int j{i+1};j < n;j++){
if(bs[j]){
ans[r-1] = j;
break;
}
}
if(!ans[r-1]){
for(int j{i-1};j >= 0;j--){
if(bs[j]){
ans[r-1] = j;
break;
}
}
}
//cout <<"a - "<< bs << endl;
return;
}
newbs[i] = 1;
}
temp[i] = '0';
}
}
find(n,l,md,newbs);
find(n,md+1,r,bs&(~newbs));
}
void add(int n,int l,int r){
string cur = "";
//cout << "po : " << l << " " << r;
for(int i{1};i < l;i++) cur += '1';
for(int i{l};i <= r;i++) cur += '0';
for(int i{r};i < n;i++) cur += '1';
int md = l+(r-l)/2;
for(int j{l};j <= md;j++){
cur[j-1] = '1';
add_element(cur);
cur[j-1] = '0';
}
}
void addall(int n,int l,int r){
//cout << l << " " << r << endl;
if(l==r) return;
add(n,l,r);
int md = l+(r-l)/2;
if(r-l > 2){
addall(n,md+1,r);
}
addall(n,l,md);
}
std::vector<int> restore_permutation(int n, int w, int r) {
addall(n,1,n);
compile_set();
bitset<N> fin;
vector<int> ret(n,0);
for(int i{};i < n;i++){
fin[i] = 1;
ans.emplace_back(0);
}
find(n,1,n,fin);
for(int i{};i < n;i++){
ret[ans[i]] = i;
}
return ret;
}
