#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
string s;
int N;
void f1(int l, int r){
int mid = (l + r) / 2;
fill(s.begin(), s.end(), '1');
for (int i = l; i <= r; i++)
{
s[i] = '0';
}
for(int i = l; i <= mid; ++i){
s[i] = '1';
add_element(s);
s[i] = '0';
}
if(l == r) return;
f1(mid + 1, r);
f1(l, mid);
}
vector<int> ans;
void f2(int l, int r){
int mid = (l + r) / 2;
fill(s.begin(), s.end(), '0');
int cnt = 0;
for (int i = 0; i < N; i++)
{
if(ans[i] == -1){
cnt++;
continue;
}
s[ans[i]] = '1';
}
int p = l;
for (int i = 0; i < N; i++)
{
if(s[i] == '1') continue;
s[i] = '1';
if(cnt == 1 || check_element(s)) ans[p++] = i;
s[i] = '0';
}
if(l == r) return;
f2(mid + 1, r);
fill(ans.begin() + l, ans.begin() + mid + 1, -1);
f2(l, mid);
}
vector<int> restore_permutation(int n, int w, int r) {
N = n;
ans.resize(n, -1);
s.resize(n);
f1(0, n - 1);
compile_set();
f2(0, n - 1);
vector<int> tmp(N);
for (int i = 0; i < N; i++)
{
tmp[ans[i]] = i;
}
return tmp;
}
