#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<set<int>>> bs;
int N;
void add_range(int l, int r)
{
string el(N, '1');
for (int i = l; i <= r; i++)
el[i] = '0';
for (int i = l; i <= (l + r) / 2; i++)
{
el[i] = '1';
add_element(el);
//cerr << el << '\n';
el[i] = '0';
}
}
void add_ranges(int l, int r)
{
if (r == l) return;
add_range(l, r);
int c = (l + r) / 2;
add_ranges(l, c);
add_ranges(c+1, r);
}
void find_range(int l, int r, int layer, int index)
{
if (r == l) return;
string el(N, '1');
for (int i = 0; i < N; i++)
{
if (bs[layer][index].count(i))
el[i] = '0';
}
for (auto i : bs[layer][index])
{
el[i] = '1';
//cerr << el << '\n';
if (check_element(el))
bs[layer+1][index*2].insert(i);
else
bs[layer+1][index*2|1].insert(i);
el[i] = '0';
}
int c = (l + r) / 2;
find_range(l, c, layer + 1, index * 2);
find_range(c+1, r, layer + 1, index * 2 | 1);
}
vector<int> restore_permutation(int n_, int W, int R)
{
N = n_;
add_ranges(0, N-1);
compile_set();
int layerCnt = __builtin_ctz(N);
bs.resize(layerCnt + 1);
for (int i = 0; i <= layerCnt; i++)
bs[i].resize(1 << i);
for (int i = 0; i < N; i++)
bs[0][0].insert(i);
find_range(0, N-1, 0, 0);
vector<int> perm(N);
for (int i = 0; i < N; i++)
{
int index = *bs[layerCnt][i].begin();
perm[index] = i;
}
return perm;
}
