#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
#define F first
#define S second
using ll=long long;
using pii=pair<int,int>;
vector<int>ans;
void generate_add(int sz, int pos, string s)
{
if(sz == 1) return;
for(int i=pos;i<pos+sz/2;i++)
{
s[i] = '1';
add_element(s);
s[i] = '0';
}
for(int i=pos+sz/2;i<pos+sz;i++) s[i] = '1';
generate_add(sz>>1, pos, s);
for(int i=pos+sz/2;i<pos+sz;i++) s[i] = '0';
s[pos] = '1';
generate_add(sz>>1, pos+sz/2, s);
s[pos] = '0';
}
void search_rescue(int sz, int pos, vector<int>res, string s)
{
//cerr<<sz<<' '<<pos<<" :";
//for(int i : res) cerr<<i<<',';cerr<<endl;
if(sz==1)
{
ans[pos] = res[0];
return;
}
vector<int> fir, sec;
for(int i=0;i<sz;i++)
{
s[res[i]] = '1';
if(check_element(s)) fir.emplace_back(res[i]);
else sec.emplace_back(res[i]);
s[res[i]] = '0';
}
for(int i : sec) s[i] = '1';
search_rescue(sz>>1, pos, fir, s);
for(int i : sec) s[i] = '0';
s[ans[pos]] = '1';
search_rescue(sz>>1, pos+sz/2, sec, s);
s[ans[pos]] = '0';
}
vector<int> restore_permutation(int n, int w, int r) {
string s = "";
vector<int>_res;
for(int i=0;i<n;i++) _res.emplace_back(i);
for(int i=0;i<n;i++) ans.emplace_back(-1);
for(int i=0;i<n;i++) s+='0';
generate_add(n,0,s);
compile_set();
search_rescue(n,0,_res,s);
//add_element("0");
//check_element("0");
vector<int>ans2(n);
for(int i=0;i<n;i++) ans2[ans[i]]=i;
return ans2;
}
