#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define ROF(i,a,b) for (int i = a; i >= b; i--)
#define pb push_back
string s = ""; int N;
void add(int l, int r){
//range l,l+1,...,r-1
if (r-l==1) return;
int mid = (l+r)/2;
FOR(i,l,mid){
s[i]='1'; add_element(s); s[i]='0';
}
FOR(i,mid,r) s[i]='1';
add(l,mid);
FOR(i,mid,r) s[i]='0';
FOR(i,l,mid) s[i]='1';
add(mid,r);
FOR(i,l,mid) s[i]='0';
}
string t;
vi get(int l, int r, vi p){
if (r-l==1) return p;
int sz = (r-l); int mid = (l+r)/2;
vi L,R;
FOR(i,0,sz){
t[p[i]]='1';
if (check_element(t)){
L.pb(p[i]);
}else{
R.pb(p[i]);
}
t[p[i]]='0';
}
for (int u : R) t[u]='1';
L = get(l,mid,L);
for (int u : R) t[u]='0';
for (int u : L) t[u]='1';
R = get(mid,r,R);
for (int u : L) t[u]='0';
vi ans = L; FOR(i,0,sz/2) ans.pb(R[i]);
return ans;
}
vi restore_permutation(int n, int w, int r) {
N=n;
FOR(i,0,n) s += "0";
FOR(i,0,n) t += "0";
add(0,n);
compile_set();
vi p(n); FOR(i,0,n) p[i]=i;
p = get(0,n,p);
vi pos(n); FOR(i,0,n) pos[p[i]]=i;
return pos;
}
