#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
void Adds(int n, int l, int r) {
if (l < r) {
int mid = (l + r) >> 1;
string s(n, '1');
for (int i = l; i <= r; ++i) {
s[i] = '0';
}
for (int i = l; i <= mid; ++i) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
Adds(n, l, mid);
Adds(n, mid + 1, r);
}
}
void Checks(int n, int l, int r, vector<int> &p) {
if (l < r) {
int mid = (l + r) >> 1;
string s(n, '1');
for (int i = l; i <= r; ++i) {
s[p[i]] = '0';
}
int i = l, j = r;
while (i <= mid) {
s[p[i]] = '1';
if (check_element(s)) {
s[p[i]] = '0';
++i;
} else {
s[p[i]] = '0';
swap(p[i], p[j]);
--j;
}
}
Checks(n, l, mid, p);
Checks(n, mid + 1, r, p);
}
}
vector<int> restore_permutation(int n, int w, int r) {
Adds(n, 0, n - 1);
compile_set();
vector<int>p(n);
for (int i = 0; i < n; ++i) {
p[i] = i;
}
Checks(n, 0, n - 1, p);
/// find inv. permutation
vector<int>q(n);
for (int i = 0; i < n; ++i) {
q[p[i]] = i;
}
return q;
}
