#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
int u;
vector<int> q, nq;
vector<bool> z;
void add(int l, int r)
{
if (r - l < 2)
return;
string s;
int i, m = (l + r) / 2;
for (i = 0; i < u; i++)
s += '1';
for (i = l; i < r; i++)
s[i] = '0';
for (i = l; i < m; i++)
{
s[i] = '1';
add_element(s);
s[i] = '0';
}
add(l, m);
add(m, r);
}
void check(int l, int r)
{
if (r - l < 2)
return;
string s;
int i, j = l, m = (l + r) / 2, k;
k = m;
for (i = 0; i < u; i++)
s += '1';
for (i = l; i < r; i++)
s[q[i]] = '0';
for (i = l; i < r; i++)
{
s[q[i]] = '1';
if (check_element(s))
{
nq[j] = q[i];
j++;
}
else
{
nq[k] = q[i];
k++;
}
s[q[i]] = '0';
}
q = nq;
check(l, m);
check(m, r);
}
vector<int> restore_permutation(int N, int w, int r)
{
int i;
u = N;
add(0, u);
compile_set();
q.resize(u);
z.resize(u);
for (i = 0; i < u; i++)
{
q[i] = i;
z[i] = 0;
}
nq = q;
check(0, u);
vector<int> an(u);
for (i = 0; i < u; i++)
an[q[i]] = i;
return an;
}
