#include "messy.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
string s;
vector <int> ans;
void ins(int l, int r, int n) {
if ( l == r )
return;
int mid = (l + r) / 2;
for (int i = 0; i < n; i++)
{
if ( i < l || i > r )
s[i] = '1';
else
s[i] = '0';
}
for (int i = l; i <= mid; i++) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
ins(l, mid, n);
ins(mid + 1, r, n);
}
void fnd(int l, int r, vector<int> x, string t) {
if ( l == r ) {
ans[x[0]] = l;
return;
}
int mid = (l + r) / 2;
string t1 = t, t2 = t;
for (int i = 0; i < t1.size(); i++)
t1[i] = '1';
for (int i = 0; i < t2.size(); i++)
t2[i] = '1';
vector <int> x1, x2;
for (int i = 0; i < x.size(); i++) {
t[x[i]] = '1';
if ( check_element(t) ) {
x1.pub(x[i]);
t1[x[i]] = '0';
} else {
x2.pub(x[i]);
t2[x[i]] = '0';
}
t[x[i]] = '0';
}
fnd(l, mid, x1, t1);
fnd(mid + 1, r, x2, t2);
}
vector<int> restore_permutation(int n, int w, int r) {
for (int i = 0; i < n; i++)
s += '0', ans.pub(i);
ins(0, n - 1, n);
compile_set();
for (int i = 0; i < n; i++)
s[i] = '0';
fnd(0, n - 1, ans, s);
return ans;
}
/*
4 16 16
2 1 3 0
*/
