#include<iostream>
#include<vector>
#include<string>
#include "messy.h"
using namespace std;
static int n, v[130];
static vector<int> sol;
void calc(int st, int dr){
if(st != dr){
int mid = (st + dr) / 2, i;
string s;
for(i = 0; i < n; i++){
if(i < st || i > dr){
s += '1';
}
else{
s += '0';
}
}
for(i = st; i <= mid; i++){
s[i] = '1';
add_element(s);
s[i] = '0';
}
calc(st, mid);
calc(mid + 1, dr);
}
}
void solve(int st, int dr, int v[]){
if(st == dr){
sol[ v[0] ] = st;
return;
}
int i, mid = (st + dr) / 2, u;
string s;
int vst[130], vdr[130];
for(i = 0; i < n; i++){
if(i < st || i > dr){
s += '1';
}
else{
s += '0';
}
}
for(i = 0; i < dr - st + 1; i++){
s[ v[i] ] = '0';
}
u = 0;
for(i = st; i <= dr; i++){
while(u < dr - st + 1 && v[u] < i){
u++;
}
if(v[u] != i){
s[i] = '1';
}
}
u = 0;
for(i = 0; i < dr - st + 1; i++){
s[ v[i] ] = '1';
if( check_element(s) ){
vst[u++] = v[i];
}
else{
vdr[i - u] = v[i];
}
s[ v[i] ] = '0';
}
solve(st, mid, vst);
solve(mid + 1, dr, vdr);
}
vector<int> restore_permutation(int N, int w, int r){
n = N;
calc(0, n - 1);
compile_set();
sol.resize(n);
for(int i = 0; i < n; i++){
v[i] = i;
}
solve(0, n - 1, v);
return sol;
}
