#include <bits/stdc++.h>
#include "messy.h"
#define ad push_back
using namespace std;
int n;
vector <int> p;
string s;
string rev(int l, int r, string s)
{
for (int i = l; i <= r; i++)
s[i] = '1' - s[i] + '0';
return s;
}
void rec1(int l, int r, string s)
{
if(l == r) return;
int md = (l + r)/2;
for (int i = l; i <= md; i++)
{
s[i] = '1';
add_element(s);
s[i] = '0';
}
s = rev(l, md, s);
rec1(md + 1, r, s);
s = rev(l, md, s);
s = rev(md + 1, r, s);
rec1(l, md, s);
}
void rec(int l, int r, string s, vector <int> sm)
{
if((int)sm.size() != r - l + 1) assert(0);
if(l == r)
{
p[l] = sm[0];
return;
}
int md = (l + r)/2;
vector <int> a, b;
for(auto p : sm)
{
s[p] = '1';
bool bl = check_element(s);
if(bl) a.ad(p);
else b.ad(p);
s[p] = '0';
}
for(auto p : b) s[p] = '1';
rec(l, md, s, a);
for(auto p : b) s[p] = '0';
for(auto p : a) s[p] = '1';
rec(md + 1, r, s, b);
}
vector<int> restore_permutation(int N, int w, int r)
{
n = N;
vector <int> sm;
for (int i = 0; i < n; i++) s += '0', sm.ad(i);
rec1(0, n - 1, s);
p.resize(n);
compile_set();
rec(0, n - 1, s, sm);
return p;
}
