#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
#define sz(s) (int)s.size()
#define mem(a,i) memset(a,i,sizeof(a))
#define pb push_back
const int MAX=2e5+10;
int lg(int n){
int cnt=0;
while(n%2==0){
n/=2;
cnt++;
}
return cnt;
}
int n,k;
bool is[MAX];
vector<int> know;
void build(int tl,int tr,int lev=-1){
if(tl==tr)return;
int tm=(tl+tr)/2;
if(lev==-1){
build(tl,tm,lev+1);
build(tm+1,tr,lev+1);
return;
}
vector<int> lef;
if(tl==0){
string s;
for(int i=0;i<n;i++)s+='1';
know.pb(tr);
for(int x:know)s[x]='0';
add_element(s);
}
string s;
for(int i=0;i<n;i++)s+='0';
for(int i=0;i<=lev;i++)s[know[i]]='1';
for(int i=tl;i<=tm;i++){
if(is[i])continue;
s[i]='1';
add_element(s);
s[i]='0';
}
build(tl,tm,lev+1);
build(tm+1,tr,lev+1);
}
int ans[MAX];
int pos[MAX];
void get_ans(int l,int r,int lev,vector<int> p){
if(l==r){
ans[p[0]]=l;
return;
}
// cerr<<l<<" "<<r<<"\n";
int m=(l+r)/2;
if(lev==-1){
vector<int> lef,rig;
string s;
for(int i=0;i<n;i++)s.pb('0');
for(int i=0;i<n;i++){
s[i]='1';
if(check_element(s)){
lef.pb(i);
}
else{
rig.pb(i);
}
s[i]='0';
}
get_ans(l,m,lev+1,lef);
get_ans(m+1,r,lev+1,rig);
return;
}
if(l==0){
string s;
for(int i=0;i<n;i++){
s.pb('1');
}
for(int x:know)s[x]='0';
for(int x:p){
s[x]='0';
if(check_element(s)){
know.pb(x);
is[x]=1;
pos[r]=x;
// cout<<r<<" "<<x<<"\n";
break;
}
s[x]='1';
}
}
vector<int> lef,rig;
string s;
for(int i=0;i<n;i++)s.pb('0');
for(int i=0;i<=lev;i++){
s[know[i]]='1';
}
for(int x:p){
if(is[x]){
if(pos[x]<=m)lef.pb(x);
else rig.pb(x);
continue;
}
s[x]='1';
if(check_element(s)){
lef.pb(x);
}
else{
rig.pb(x);
}
s[x]='0';
}
// cerr<<l<<" "<<r<<" "<<sz(p)<<" "<<sz(lef)<<" "<<sz(rig)<<"\n";
get_ans(l,m,lev+1,lef);
get_ans(m+1,r,lev+1,rig);
}
vector<int> restore_permutation(int N, int w, int r) {
n=N;
k=6;
build(0,n-1);
string s;
for(int i=0;i<n;i++)s.pb('0');
for(int i=0;i<n/2;i++){
s[i]='1';
add_element(s);
s[i]='0';
}
compile_set();
{
know.clear();
vector<int> cur;
for(int i=0;i<n;i++)cur.pb(i);
mem(is,0);
get_ans(0,n-1,-1,cur);
vector<int> res;
for(int i=0;i<n;i++){
res.pb(ans[i]);
}
return res;
}
}
