#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
#include<random>
#include<bitset>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<deque>
#include<chrono>
#include "messy.h"
using namespace std;
typedef long long int lld;
typedef long double lf;
#define INF 1000000000000000000LL
#define MOD 998244353
#define ff first
#define ss second
int n;
vector<int> perm;
void add_elems(int l, int r){
if(r<=l) return;
int mid = (l+r)/2;
string s(n, '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';
}
add_elems(l, mid);
add_elems(mid+1, r);
return;
}
void compute_perm(int l, int r){
if(r<=l) return;
string s(n, '1');
for(int i=l;i<=r;i++) s[perm[i]] = '0';
vector<int> new_perm;
set<int> old_perm;
for(int i=l;i<=r;i++){
old_perm.insert(perm[i]);
s[perm[i]] = '1';
if(check_element(s)) new_perm.push_back(perm[i]);
s[perm[i]] = '0';
}
int mid = (l+r)/2;
for(int i=l;i<=mid;i++){
perm[i] = new_perm[i-l];
old_perm.erase(new_perm[i-l]);
}
auto it = old_perm.begin();
for(int i=mid+1;i<=r;i++){
perm[i] = *it;
it++;
}
compute_perm(l, mid);
compute_perm(mid+1, r);
return;
}
vector<int> restore_permutation(int N, int W, int R){
n = N;
add_elems(0, n-1);
compile_set();
for(int i=0;i<n;i++) perm.push_back(i);
compute_perm(0, n-1);
vector<int> inv_perm(n);
for(int i=0;i<n;i++) inv_perm[perm[i]] = i;
return inv_perm;
}
