#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
template<typename T>
auto operator<<(ostream &os, T&v)->decltype(v.begin(), os){
os << "[";
int f = 0;
for(auto i:v) {
if(f++)os << ", ";
os << i;
}
os << "]";
return os;
}
template<typename F, typename S>
ostream& operator<<(ostream &os, pair<F, S> const &p) {
return os << "(" << p.first << ", " << p.second << ")";
}
ostream& operator<<(ostream &os, string& s) {
for(char i:s){
os << i;
}
return os;
}
void debug(){}
template<typename T, typename... V>
void debug(T t, V... v) {
cerr << t;
if(sizeof...(v)) {
cerr << ", "; debug(v...);
}
}
#ifdef LOCAL
#define dbg(x...) cerr << "[" << #x << "]: " << "["; debug(x); cerr << "]\n";
#else
#define dbg(x...)
#endif
string s = "";
int na;
vector<int> ans;
void fill(int l, int r, char c) {
for(int i = l;i<=r;i++) {
s[i] = c;
}
}
void add(int l, int r) {
if(l == r)return;
fill(0, na-1, '0');
fill(0, l-1, '1');
fill(r+1, na-1, '1');
int mid = (l+r)/2;
dbg(l, r);
for(int i = l;i<=mid;i++) {
s[i] = '1';
dbg("ADD",s);
add_element(s);
s[i] = '0';
}
add(l, mid);
add(mid+1, r);
}
void solve(vector<int> &v, int l, int r) {
dbg(l, r, v);
if(l == r) {
ans[v[0]] = l;
return;
}
fill(0, na-1, '0');
fill(0, l-1, '1');
fill(r+1, na-1, '1');
int mid = (l+r)>>1ll;
vector<int> left, right;
fill(0, na-1, '1');
for(int i:v)s[i] = '0';
for(int i:v) {
s[i] = '1';
bool check = check_element(s);
dbg(i, s, check);
if(check) {
left.push_back(i);
}
else right.push_back(i);
s[i] = '0';
}
solve(left, l, mid);
solve(right, mid+1, r);
}
vector<int> restore_permutation(int N, int w, int r) {
na = N;
for(int i = 0;i<na;i++)s+="0";
vector<int> v(na);
ans.resize(na);
iota(v.begin(), v.end(), 0);
add(0, na-1);
compile_set();
solve(v, 0, na-1);
return ans;
}
