#include "bits/stdc++.h"
#include "messy.h"
using namespace std;
const int sz = 256;
vector<string> qry;
int an[sz];
int n;
map<string,bool> mp;
bool Ask(string s) {
if (mp.count(s)) return mp[s];
return mp[s] = check_element(s);
}
void gen_qry(int le, int ri) {
int mi = le + (ri - le) / 2;
string p(le - 1, '1');
string s(n - ri, '1');
string b(mi - le + 1, '0');
string f(ri - mi, '0');
for (int i = le; i <= mi; i ++) {
b[i - le] = '1';
qry.push_back(p + b + f + s);
b[i - le] = '0';
}
if (le == ri) return;
gen_qry(le, mi);
gen_qry(mi + 1, ri);
}
void solve(int le, int ri, vector<int> bl) {
if (le == ri) {
map<int,bool> cn;
for (int ix : bl) cn[ix];
for (int i = 0; i < n; i ++) if (!cn.count(i)) an[i] = le - 1;
return;
}
int mi = le + (ri - le) / 2;
string s(n, '0');
for (int ix : bl)
s[ix] = '1';
vector<int> ls;
for (int i = 0; i < n; i ++)
if ('0' == s[i]) {
s[i] = '1';
bool f = Ask(s);
if (!f) bl.push_back(i);
else ls.push_back(i);
s[i] = '0';
}
solve(le, mi, bl);
int m = mi - le + 1;
for (int i = 0; i < m; i ++) bl.pop_back();
for (int ix : ls) bl.push_back(ix);
solve(mi + 1, ri, bl);
}
vector<int> restore_permutation(int N, int w, int r) {
n = N;
gen_qry(1, n);
for (auto s : qry)
add_element(s);
compile_set();
solve(1, n, {});
vector<int> p;
for (int i = 0; i < n; i ++)
p.push_back(an[i]);
return p;
}
