#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
int n;
void go(int l, int r){
if (l == r) return;
int m = (l + r) >> 1;
string s(n, '1');
for (int i = l; i <= m; i++) s[i] = '0';
add_element(s);
//cout << s << endl;
go(l, m);
go(m + 1, r);
}
set<string> myset;
vector<int> ans;
void go2(int l, int r){
if (!ans.empty()) return;
if (l == r) return;
int m = (l + r) >> 1;
string s(n, '1');
for (int i = l; i <= m; i++) s[i] = '0';
for (int i = l; i <= m; i++){
for (int j = m + 1; j <= r; j++){
string t = s;
swap(t[i], t[j]);
if (myset.find(t) != myset.end()){
for (int i = 0; i < n; i++) ans.push_back(i);
swap(ans[i], ans[j]);
return;
}
}
}
go2(l, m);
go2(m + 1, r);
}
std::vector<int> restore_permutation(int _n, int w, int r) {
n = _n;
go(0, n - 1);
compile_set();
for (int mask = 0; mask < (1 << n); mask++){
string s;
for (int i = 0; i < n; i++){
s += ((mask & (1 << i)) ? '1' : '0');
}
if (check_element(s)){
myset.insert(s);
}
}
go2(0, n - 1);
return ans;
}
/*
8 256 256
0 1 5 3 4 2 6 7
*/
