#include <vector>
#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
int sz;
void add(int mask) {
string s;
for(int i = 0; i < sz; i++) {
s += (mask >> i & 1) + '0';
}
add_element(s);
}
bool check(int mask) {
string s;
for(int i = 0; i < sz; i++) {
s += (mask >> i & 1) + '0';
}
return check_element(s);
}
int popcount(int mask) {
return __builtin_popcount(mask);
}
std::vector<int> restore_permutation(int n, int w, int r) {
sz = n;
{
auto dnc = [&](auto &&self, vector<int> a) -> void {
if(a.size() == 1) return;
vector<int> a1, a2;
int mask = 0;
for(int i = 0; i < (int)a.size(); i++) {
if(i & 1) {
mask |= (1 << a[i]);
a1.push_back(a[i]);
} else {
a2.push_back(a[i]);
}
}
add(mask);
// cout << "mask: " << bitset<8>(mask) << nl;
self(self, a1);
self(self, a2);
};
vector<int> a(n);
iota(a.begin(), a.end(), 0);
dnc(dnc, a);
}
compile_set();
set<int> st;
for(int mask = 0; mask < (1 << n); mask++) {
if(check(mask)) st.emplace(mask);
}
vector<int> p(n);
iota(p.begin(), p.end(), 0);
auto dif = [&](int m1, int m2) {
vector<int> ind;
for(int i = 0; i < n; i++) {
if((m1 >> i & 1) != (m2 >> i & 1)) ind.push_back(i);
}
if(ind.empty()) return;
swap(p[ind[0]], p[ind[1]]);
};
int fmask = -1;
{
auto dnc = [&](auto &&self, vector<int> a) -> void {
if(a.size() == 1) return;
vector<int> a1, a2;
int mask = 0;
for(int i = 0; i < (int)a.size(); i++) {
if(i & 1) {
mask |= (1 << a[i]);
a1.push_back(a[i]);
} else {
a2.push_back(a[i]);
}
}
if(st.count(mask)) {
st.erase(mask);
self(self, a1);
self(self, a2);
} else {
fmask = mask;
}
};
vector<int> a(n);
iota(a.begin(), a.end(), 0);
dnc(dnc, a);
}
if(fmask != -1) {
// cout << bitset<8>(fmask) << nl;
for(auto mask : st) {
if(popcount(mask) == popcount(fmask)) {
dif(mask, fmask);
break;
}
}
}
return p;
}
