#include "messy.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define sc second
#define fr first
#define mk make_pair
#define pb push_back
using namespace std;
const int N = (1e6 + 5);
const int inf = (1e9 + 7);
string s;
vector <int> ans,res;
void fun(int n,int l,int r) {
if (l >= r) return;
s = "";
for (int i = 0; i <= n; i ++) {
if (l <= i && i <= r) s += '0';
else s += '1';
}
int md = (l + r) >> 1;
for (int i = l; i <= md; i ++) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
fun(n,l,md);
fun(n,md + 1,r);
}
void rec(int n,int l,int r) {
if (l >= r) return;
s = "";
for (int i = 0; i <= n; i ++) s += '0';
for (int i = 0; i <= n; i ++) {
if (l <= i && i <= r) s[ans[i]] = '0';
else s[ans[i]] = '1';
}
int md = (l + r) >> 1;
vector <int> v1,v2;
for (int i = l; i <= r; i ++) {
s[ans[i]] = '1';
if (check_element(s))
v1.pb(ans[i]);
else
v2.pb(ans[i]);
s[ans[i]] = '0';
}
int id = 0,id1 = 0;
for (int i = l; i <= r; i ++) {
if (i <= md) ans[i] = v1[id ++];
else ans[i] = v2[id1 ++];
}
rec(n,l,md);
rec(n,md + 1,r);
}
vector<int> restore_permutation(int n, int w, int r) {
ans.resize(n);
res.resize(n);
n --;
for (int i = 0; i <= n; i ++)
ans[i] = i;
fun(n,0,n);
compile_set();
rec(n,0,n);
for (int i = 0; i <= n; i ++)
res[ans[i]] = i;
return res;
}
