#include <bits/stdc++.h>
using namespace std;
#include "messy.h"
//#include "grader.cpp"
#define mid ((l + r) >> 1)
mt19937 rng (chrono::steady_clock::now().time_since_epoch().count());
int random (int l, int r) {
return uniform_int_distribution <int> (l, r) (rng);
}
int n;
void recurse (int l, int r) {
if (l == r) {
return;
}
string t;
for (int i = 0; i < n; i++) {
t += '1';
}
for (int i = l; i <= r; i++) {
t[i] = '0';
}
for (int i = l; i <= mid; i++) {
t[i] = '1';
add_element(t);
t[i] = '0';
}
recurse(l, mid); recurse(mid + 1, r);
}
vector <int> P;
void construct (int l, int r, vector <int> x) {
if (l == r) {
P[x[0]] = l;
return;
}
string t;
for (int i = 0; i < n; i++) {
t.push_back('1');
}
for (auto j : x) {
t[j] = '0';
}
vector <int> g, h;
for (auto j : x) {
t[j] = '1';
if (check_element(t)) {
g.push_back(j);
} else {
h.push_back(j);
}
t[j] = '0';
}
construct(l, mid, g); construct(mid + 1, r, h);
}
vector <int> restore_permutation (int N, int w, int r) {
n = N;
P.resize(n);
recurse(0, n - 1);
compile_set();
vector <int> z;
for (int i = 0; i < n; i++) {
z.push_back(i);
}
construct(0, n - 1, z);
return P;
}
