#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
int n;
void add (int l = 0, int r = n - 1) {
if (l == r) {
return;
}
string s = string(l, '1') + string(r - l + 1, '0') + string(n - r - 1, '1');
int mid = (l + r) / 2;
for (int i = l; i <= mid; ++i) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
add(l, mid);
add(mid + 1, r);
}
void check (int l, int r, vector<int> M, vector<int> &p) {
if (l == r) {
p[M[0]] = l;
return;
}
string s = string(n, '1');
for (int i : M) {
s[i] = '0';
}
int mid = (l + r) / 2;
vector<int> L, R;
for (int i : M) {
s[i] = '1';
(check_element(s) ? L : R).push_back(i);
s[i] = '0';
}
check(l, mid, L, p);
check(mid + 1, r, R, p);
}
vector<int> restore_permutation(int n, int w, int r) {
::n = n;
vector<int> p(n);
iota(p.begin(), p.end(), 0);
add();
compile_set();
check(0, n - 1, p, p);
return p;
}
