#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
using pii = pair<int, int>;
const int N = 128;
const int LN = 7;
int n, ln, ans[N][LN]; // 1 = left, 0 = right
string construct(int l, int r, int ca)
{
string s(n, '0');
for (int i = 0; i < l; ++i)
s[i] = i < ca ? '1' : '0';
for (int i = n-1; i > r; --i)
s[i] = '1';
return s;
}
void build_tree(int l, int r, int ca)
{
if (l == r) return;
string s = construct(l, r, ca);
int m = (l+r)/2;
for (int i = l; i <= m; ++i) {
string t(s);
t[i] = '1';
add_element(t);
}
build_tree(l, m, ca);
build_tree(m+1, r, ca+1);
}
pii getrange(int i)
{
int l = 0, r = n-1;
for (int j = 0; j < ln; ++j) {
if (ans[i][j] == -1) break;
int m = (l+r)/2;
if (ans[i][j] == 1) r = m;
else l = m+1;
}
return pii(l, r);
}
void query_tree(int l, int r, int ca, int dep)
{
if (l == r) return;
string s = construct(l, r, ca);
string q(n, '0');
for (int i = 0; i < n; ++i) {
pii ri = getrange(i);
if (ri != pii(l, r))
q[i] = s[ri.first];
}
for (int i = 0; i < n; ++i) {
pii ri = getrange(i);
if (ri == pii(l, r)) {
string t(q);
t[i] = '1';
bool ret = check_element(t);
ans[i][dep] = ret?1:0;
}
}
int m = (l+r)/2;
query_tree(l, m, ca, dep+1);
query_tree(m+1, r, ca+1, dep+1);
}
vector<int> restore_permutation(int n, int w, int r)
{
::n = n;
ln = 0;
while ((1<<ln) < n) ++ln;
for (int i = 0; i < n; ++i) for (int j = 0; j < ln; ++j)
ans[i][j] = -1;
build_tree(0, n-1, 0);
compile_set();
query_tree(0, n-1, 0, 0);
vector<int> ans;
for (int i = 0; i < n; ++i)
ans.push_back(getrange(i).first);
return ans;
}
