//雪花飄飄北風嘯嘯
//天地一片蒼茫
#include "messy.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n;
void dnc_w(vector<int> proc){
if (sz(proc)==1) return;
set<int> in;
for (auto &it:proc) in.insert(it);
string s(n,'0');
rep(x,0,n) if (!in.count(x)) s[x]='1';
rep(x,0,sz(proc)/2){
s[proc[x]]='1';
add_element(s);
s[proc[x]]='0';
}
vector<int> l,r;
rep(x,0,sz(proc)/2) l.pub(proc[x]);
rep(x,sz(proc)/2,sz(proc)) r.pub(proc[x]);
dnc_w(l),dnc_w(r);
}
vector<int> ans;
void dnc_r(vector<int> proc,vector<int> val){
if (sz(proc)==1){
ans[proc[0]]=val[0];
return;
}
set<int> in;
for (auto &it:proc) in.insert(it);
string s(n,'0');
rep(x,0,n) if (!in.count(x)) s[x]='1';
vector<int> l,r;
vector<int> lval,rval;
rep(x,0,sz(proc)){
s[proc[x]]='1';
if (check_element(s)) l.pub(proc[x]);
else r.pub(proc[x]);
s[proc[x]]='0';
}
rep(x,0,sz(proc)/2) lval.pub(val[x]);
rep(x,sz(proc)/2,sz(proc)) rval.pub(val[x]);
dnc_r(l,lval),dnc_r(r,rval);
}
std::vector<int> restore_permutation(int N,int W,int R) {
n=N;
rep(x,0,n) ans.pub(0);
vector<int> proc;
rep(x,0,n) proc.pub(x);
dnc_w(proc);
compile_set();
dnc_r(proc,proc);
return ans;
}
