#include <vector>
#include <iostream>
#include <string>
#include "messy.h"
using namespace std;
void recurseAdd(int left, int right, string &cur) { // [left, right]
int mid = (left + right) / 2;
for (int i = left; i <= mid; ++i) {
cur[i] = '1';
add_element(cur);
// cout << cur << endl;
cur[i] = '0';
}
if (left == right - 1) return;
for (int i = left; i <= mid; ++i) cur[i] = '1';
recurseAdd(mid + 1, right, cur);
for (int i = left; i <= mid; ++i) cur[i] = '0';
for (int i = mid + 1; i <= right; ++i) cur[i] = '1';
recurseAdd(left, mid, cur);
for (int i = mid + 1; i <= right; ++i) cur[i] = '0';
}
void recurseQuery(int left, int right, vector<int> &p, string &cur) {
// for(int &i : p) cout << i << ' ';
// cout << endl;
vector<int> cop(right + 1, -1);
for (int i = left; i <= right; ++i) cop[i] = p[i];
int cur1 = left, cur2 = (left + right) / 2 + 1;
for (int i = left; i <= right; ++i) {
cur[cop[i]] = '1';
// cout << cur << endl;
if (check_element(cur)) p[cur1++] = cop[i];
else p[cur2++] = cop[i];
cur[cop[i]] = '0';
}
// for(int &i : p) cout << i << ' ';
// cout << endl;
if (left == right - 1) return;
int mid = (left + right) / 2;
for (int i = left; i <= mid; ++i) cur[p[i]] = '1';
recurseQuery(mid + 1, right, p, cur);
for (int i = left; i <= mid; ++i) cur[p[i]] = '0';
for (int i = mid + 1; i <= right; ++i) cur[p[i]] = '1';
recurseQuery(left, mid, p, cur);
for (int i = mid + 1; i <= right; ++i) cur[p[i]] = '0';
}
std::vector<int> restore_permutation(int n, int w, int r) {
string str = "";
for (int i = 0; i < n; ++i) str += '0';
recurseAdd(0, n - 1, str);
compile_set();
vector<int> p(n);
for (int i = 0; i < n; ++i) p[i] = i;
recurseQuery(0, n - 1, p, str);
vector<int> res(n, -1);
for (int i = 0; i < n; ++i) res[p[i]] = i;
return res;
}
