#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
void divideAdd(int l, int r, string hint) {
if (l == r) {
return;
}
int mid = (l + r) / 2;
for (int i = l; i <= mid; ++i) {
hint[i] = '1';
add_element(hint);
hint[i] = '0';
}
for (int i = mid + 1; i <= r; ++i) {
hint[i] = '1';
}
divideAdd(l, mid, hint);
for (int i = mid + 1; i <= r; ++i) {
hint[i] = '0';
}
for (int i = l; i <= mid; ++i) {
hint[i] = '1';
}
divideAdd(mid + 1, r, hint);
}
vector<int> perm;
void divideRestore(int l, int r, string hint, const vector<int> &pos) {
if (l == r) {
perm[pos[0]] = l;
return;
}
vector<int> left, right;
for (const int &p : pos) {
hint[p] = '1';
if ((int)left.size() == (r - l + 1) / 2) {
right.emplace_back(p);
} else if ((int)right.size() == (r - l + 1) / 2 || check_element(hint)) {
left.emplace_back(p);
} else {
right.emplace_back(p);
}
hint[p] = '0';
}
int mid = (l + r) / 2;
for (const int &p : right) {
hint[p] = '1';
}
divideRestore(l, mid, hint, left);
for (const int &p : right) {
hint[p] = '0';
}
for (const int &p : left) {
hint[p] = '1';
}
divideRestore(mid + 1, r, hint, right);
}
vector<int> restore_permutation(int n, int w, int r) {
divideAdd(0, n - 1, string(n, '0'));
compile_set();
vector<int> pos(n);
iota(pos.begin(), pos.end(), 0);
random_shuffle(pos.begin(), pos.end());
perm.resize(n);
divideRestore(0, n - 1, string(n, '0'), pos);
return perm;
}
