#include <bits/stdc++.h>
using namespace std;
#include "messy.h"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
//#define endl "\n"
#define sp " "
int ress[20005], N, vis[20005];
void f(int lvl, int l, int r, vector<int> pos){
if (l == r)
{
if (pos.empty()){
//cout<<"!!!!"<<endl;
return;
}
ress[l] = pos.front();
return;
}
int mid = (l + r) / 2;
string curr(N, '0');
int P = lvl;
curr[ress[P]] = '1';
// you could optimize by using the same element inverted and not inverted, cuts the element count by half
vector<int> lft, rgt;
vector<int> done(N, 0);
for (int i = l; i <= mid; i++){
if (vis[i]){
lft.pb(ress[i]);
done[ress[i]] = 1;
}
}
for (auto j: pos){
if (done[j]) continue;
curr[j] = '1';
if (check_element(curr)){
lft.pb(j);
done[j] = 1;
}
curr[j] = '0';
}
for (auto i : pos)
if (!done[i]) rgt.pb(i);
f(lvl + 1, l, mid, lft);
f(lvl + 1, mid + 1, r, rgt);
}
void g(int lvl, int l, int r){
if (l == r) return;
int mid = (l + r) / 2;
string curr(N, '0');
int P = lvl;
curr[P] = '1';
for (int i = l; i <= mid; i++){
if (vis[i] == 0){
curr[i] = '1';
add_element(curr);
curr[i] = '0';
}
}
g(lvl + 1, l, mid);
g(lvl + 1, mid + 1, r);
}
vector<int> restore_permutation(int n, int w, int r) {
N = n;
int lg = 0;
while((1<<lg) < n) lg++;
//cout<<lg<<endl;
string curr(n, '1');
for (int i = 0; i < lg; i++)
{
vis[i] = 1;
curr[i] = '0';
//cout<<"adding : "<<curr<<endl;
add_element(curr);
}
g(0, 0, n - 1);
compile_set();
curr = string(n, '1');
for (int i = 0; i < lg; i++){
for (int j = 0; j < n; j++){
if (curr[j] == '0') continue;
curr[j] = '0';
int res = check_element(curr);
if (res){
ress[i] = j;
break;
}
curr[j] = '1';
}
}
vector<int> v(n);
iota(v.begin(), v.end(), 0);
f(0, 0, n - 1, v);
vector<int> ans(n);
for (int i = 0; i < n; i++){
ans[ress[i]] = i;
}
return ans;
}
