#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
typedef long long ll;
vector<int> ans;
int n;
void dnc_write(int l, int r){
if (r-l<=1) return;
string s;
int m = (l+r)>>1;
for (int i=0;i<n;i++){
if (i<l || i>=r) s.push_back('1');
else s.push_back('0');
}
for (int i=l;i<m;i++){
s[i] = '1';
add_element(s);
s[i] = '0';
}
dnc_write(l, m);
dnc_write(m, r);
}
void dnc_read(int l, int r, vector<int> x){
if (r-l<=1){
ans[x[0]] = l; return;
}
string s(n, '1');
for (auto &y:x) s[y] = '0';
vector<int> L, R;
for (int i=0;i<r-l;i++){
s[x[i]] = '1';
if (check_element(s)) L.push_back(x[i]);
else R.push_back(x[i]);
s[x[i]] = '0';
}
int m = (l+r)>>1;
dnc_read(l, m, L); dnc_read(m, r, R);
}
vector<int> restore_permutation(int N, int w, int r) {
n = N;
ans.resize(n);
dnc_write(0, n);
compile_set();
vector<int> tmp;
for (int i=0;i<n;i++) tmp.push_back(i);
dnc_read(0, n, tmp);
return ans;
}
