#include<bits/stdc++.h>
#include<messy.h>
using namespace std;
string voll="";
void insert(int n, vector<int>& a){
if(a.size()<=1) return;
/*cout << a.size() << "\n";
for(auto e: a){
cout << e << " ";
}
cout << "\n";*/
string x=voll;
for(auto e: a){
x[e]='0';
}
for(int i=0; i<(int)a.size()/2; i++){
x[a[i]]='1';
add_element(x);
x[a[i]]='0';
}
vector<int> a1;
vector<int> a2;
for(int i=0; i<(int)a.size(); i++){
if(i<(int)a.size()/2){
a1.push_back(a[i]);
}
else{
a2.push_back(a[i]);
}
}
insert(n, a1);
insert(n, a2);
}
void solve(int n, vector<int>& a, vector<int>& b, vector<int>& p){
if(a.size()==1){
p[b[0]]=a[0];
return;
}
string x=voll;
vector<int> b1;
vector<int> b2;
for(auto e: b){
x[e]='0';
}
for(auto e: b){
x[e]='1';
if(check_element(x)){
b1.push_back(e);
}
else{
b2.push_back(e);
}
x[e]='0';
}
vector<int> a1;
vector<int> a2;
for(int i=0; i<(int)a.size(); i++){
if(i<(int)a.size()/2){
a1.push_back(a[i]);
}
else{
a2.push_back(a[i]);
}
}
solve(n, a1, b1, p);
solve(n, a2, b2, p);
}
vector<int> restore_permutation(int n, int w, int r){
vector<int> b(n);
iota(b.begin(), b.end(), 0);
vector<int> a(n);
iota(a.begin(), a.end(), 0);
for(int i=0; i<n; i++){
voll+="1";
}
insert(n, a);
compile_set();
vector<int> p(n);
solve(n, a, b, p);
return p;
}
