#include <vector>
#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
int n;
string s;
void build(int l, int r){
if (l + 1 == r) return;
int mid = (l + r) >> 1;
for (int i = l; i < mid; i++){
s[i] = '1';
//debug(s);
add_element(s);
s[i] = '0';
}
for (int i = mid; i < r; i++){
s[i] = '1';
}
build(l, mid);
for (int i = mid; i < r; i++){
s[i] = '0';
}
for (int i = l; i < mid; i++){
s[i] = '1';
}
build(mid, r);
for (int i = l; i < mid; i++){
s[i] = '0';
}
}
const int maxn = 1e5 + 10;
int p[maxn];
void solve(vector<int> idx, int l, int r){
if (l + 1 == r){
p[idx[0]] = l;
return;
}
vector<int> lc, rc;
for (auto x: idx){
s[x] = '1';
if (check_element(s)) lc.push_back(x);
else rc.push_back(x);
s[x] = '0';
}
int mid = (l + r) >> 1;
for (auto x: rc) s[x] = '1';
solve(lc, l, mid);
for (auto x: rc) s[x] = '0';
for (auto x: lc) s[x] = '1';
solve(rc, mid, r);
for (auto x: lc) s[x] = '0';
}
vector<int> restore_permutation(int N, int w, int r) {
n = N;
for (int i = 0; i < n; i++) s.push_back('0');
build(0, n);
compile_set();
vector<int> idx;
for (int i = 0; i < n; i++){
idx.push_back(i);
}
solve(idx, 0, n);
vector<int> ans(n);
for (int i = 0; i < n; i++) ans[i] = p[i];
return ans;
}
