#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define pb push_back
vector<int> p;
void da(int l, int r, string base, int n) {
if(l==r) return;
int mid = (l+r)/2;
string cp = base, cp2 = base;
rep(i,l,mid) {
base[i] = '1';
cp[i] = '1';
add_element(base);
base[i] = '0';
}
rep(i,mid+1,r) cp2[i] = '1';
da(l,mid,cp2,n);
da(mid+1,r,cp,n);
}
void dc(int l, int r, vector<int> mb, string base, int n) {
if(l==r) {
p[mb[0]] = l;
return;
}
int mid = (l+r)/2;
string cp = base, cp2 = base;
vector<int> nmb[2];
for(int &i : mb) {
base[i] = '1';
if(check_element(base)) {
nmb[0].pb(i);
cp[i] = '1';
}
else {
nmb[1].pb(i);
cp2[i] = '1';
}
base[i] = '0';
}
dc(l,mid,nmb[0],cp2,n);
dc(mid+1,r,nmb[1],cp,n);
}
// all my homies love divide and conquer
vector<int> restore_permutation(int n, int w, int r) {
// só colocar umas string mt fodas ai
p.resize(n,0);
vector<int> evr;
string base = "";
rep(i,0,n-1) {
base+='0';
evr.pb(i);
}
da(0,n-1,base, n);
compile_set();
rep(i,0,n-1) base[i] = '0';
dc(0,n-1,evr,base, n);
return p;
}
