#include <vector>
#include<bits/stdc++.h>
using namespace std;
#include "messy.h"
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){return a.size();}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
auto shuffle(vector<int>&a){
int n = a.size();
random_shuffle(all(a));
for(int i = 0; i < n; i ++){
int ii = rng() % n, jj = rng() % n;
while(ii == jj) jj = rng() % n;
swap(a[ii], a[jj]);
}
}
void add(int n, int l, int r){
if(l == r) return;
string s = string(n, '0');
for(int i = l; i <= r; i ++) s[i] = '1';
int m = (l + r) / 2;
for(int i = l; i <= m; i ++){
s[i] = '0';
add_element(s);
s[i] = '1';
}
add(n, l, m);
add(n, m + 1, r);
}
void restore(vector<int> &perm, string s){
if(len(perm) == 1) return;
//for(auto u : perm) cout << u << ' ';
//cout << endl;
vector<int> lef, rig;
for(auto i : perm){
s[i] = '0';
if(check_element(s)) lef.push_back(i);
else rig.push_back(i);
s[i] = '1';
}
//for(auto u : lef) cout << u << ' ';
// cout << endl;
for(auto i : rig) s[i] = '0';
restore(lef, s);
for(auto i : rig) s[i] = '1';
for(auto i : lef) s[i] = '0';
restore(rig, s);
for(auto i : lef) s[i] = '1';
perm = lef;
for(auto i : rig) perm.push_back(i);
}
vector<int> restore_permutation(int n, int w, int r) {
add(n, 0, n - 1);
compile_set();
vector<int> perm(n);
iota(all(perm), 0);
string s(n, '1');
restore(perm, s);
vector<int> ans(n);
for(int i = 0; i < n; i ++) ans[perm[i]] = i;
return ans;
};
