#include "messy.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> ans;
int n;
void build(int l, int r) {
if (l == r) {
return;
}
int m = (l+r)/2;
string s(n, '1');
for (int i = l; i <= r; i++) {
s[i] = '0';
}
for (int i = l; i <= m; i++) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
build(l, m);
build(m+1, r);
}
void calc(int l, int r, vector<int> a) {
if (l == r) {
ans[a[0]] = l;
return;
}
int m = (l+r)/2;
vector<int> le, ri;
string s(n, '1');
for (int i : a) {
s[i] = '0';
}
for (int i : a) {
s[i] = '1';
if (check_element(s)) {
le.push_back(i);
} else {
ri.push_back(i);
}
s[i] = '0';
}
calc(l, m, le);
calc(m+1, r, ri);
}
vector<int> restore_permutation(int N, int w, int r) {
n = N;
ans.resize(n);
build(0, n-1);
compile_set();
vector<int> a;
for (int i = 0; i < n; i++) {
a.push_back(i);
}
calc(0, n-1, a);
return ans;
}
