#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
string zer;
vector<int>ds, ans;
int N;
void dq(int l, int r, string cur){
if (l == r)
return;
int mid = (l + r) >> 1;
for (int i = l; i <= mid; i++){
cur[i] = '1';
add_element(cur);
cur[i] = '0';
}
for (int i = l; i <= mid; i++)
cur[i] = '1';
dq(mid + 1, r, cur);
for (int i = 0; i < N; i++)
cur[i] = '0' + '1' - cur[i];
dq(l, mid, cur);
}
void calc(int l, int r, vector<int> vt, string cur){
if (l == r){
ans[*vt.begin()] = l;
return;
}
int mid = (l + r) >> 1;
vector<int>lc, rc;
random_shuffle(vt.begin(), vt.end());
for (int tmp : vt){
cur[tmp] = '1';
if ((int)lc.size() != mid - l + 1 && check_element(cur))
lc.push_back(tmp);
else
rc.push_back(tmp);
cur[tmp] = '0';
}
for (int tmp : lc)
cur[tmp] = '1';
calc(mid + 1, r, rc, cur);
for (int i = 0; i < N; i++)
cur[i] = '0' + '1' - cur[i];
calc(l, mid, lc, cur);
}
std::vector<int> restore_permutation(int n, int w, int r) {
N = n;
ans.resize(n);
zer.resize(n, '0');
dq(0, n - 1, zer);
compile_set();
for (int i = 0; i < n; i++)
ds.push_back(i);
calc(0, n - 1, ds, zer);
return ans;
}
