#include<bits/stdc++.h>
#include "messy.h"
#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 210, mod = 1e9 + 7, inf = 1e9 + 10;
string s;
void go_add(int l, int r){
if(r-l <= 2)
return;
int mid = (l+r) >> 1;
for(int i = l; i < mid; i++)
s[i] = '1';
int MID = (mid + r) >> 1;
for(int i = MID; i < r; i++){
s[i] = '1';
add_element(s);
s[i] = '0';
}
for(int i = l; i < mid; i++)
s[i] = '0';
for(int i = mid; i < r; i++)
s[i] = '1';
MID = (l + mid) >> 1;
for(int i = MID; i < mid; i++){
s[i] = '1';
add_element(s);
s[i] = '0';
}
for(int i = mid; i < r; i++)
s[i] = '0';
go_add(l, mid);
go_add(mid, r);
}
vector<int> ans;
void go_check(vector<int> ZR, vector<int> ON, int l, int r){
if(r-l <= 2){
assert(r-l == 2);
assert(sz(ZR) == 1);
assert(sz(ON) == 1);
ans[ZR[0]] = l;
ans[ON[0]] = l+1;
return;
}
int mid = (l+r) >> 1;
vector<int> _ZR, _ON;
for(int x : ZR)
s[x] = '1';
for(int x : ON){
s[x] = '1';
if(check_element(s))
_ON.PB(x);
else
_ZR.PB(x);
s[x] = '0';
}
for(int x : ZR)
s[x] = '0';
go_check(_ZR, _ON, mid, r);
_ZR.clear(), _ON.clear();
for(int x : ON)
s[x] = '1';
for(int x : ZR){
s[x] = '1';
if(check_element(s))
_ON.PB(x);
else
_ZR.PB(x);
s[x] = '0';
}
for(int x : ON)
s[x] = '0';
go_check(_ZR, _ON, l, mid);
}
vector<int> restore_permutation(int n, int w, int r){
for(int i = 0; i < n; i++)
s.PB('0');
for(int i = (n/2); i < n; i++){
s[i] = '1';
add_element(s);
s[i] = '0';
}
go_add(0, n);
compile_set();
vector<int> ZR, ON;
for(int i = 0; i < n; i++){
s[i] = '1';
if(check_element(s))
ON.PB(i);
else
ZR.PB(i);
s[i] = '0';
}
ans.resize(n);
go_check(ZR, ON, 0, n);
return ans;
}
