#include "messy.h"
#include <iostream>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
// using mii = gp_hash_table<int, int>;
// typedef tree<pii, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define sz(x) (int) (x).size()
#define all(x) x.begin(), x.end()
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;
const int MN = 1e5 + 2, LN = 17;
int N;
vector<int> f;
void init(int l, int r) {
if (l == r) return;
int m = (l + r) / 2;
string s(N, '1');
for (int i = l; i <= r; i++) s[i] = '0';
for (int i = l; i <= m; i++) {
s[i] = '1';
add_element(s);
s[i] = '0';
}
init(l, m);
init(m + 1, r);
}
void go(int l, int r, vector<int> v) {
if (l == r) {
f[v[0]] = l;
return;
}
int m = (l + r) / 2;
string s(N, '1');
vector<int> left, right;
for (int i : v) s[i] = '0';
for (int i : v) {
s[i] = '1';
if (check_element(s)) left.pb(i);
else right.pb(i);
s[i] = '0';
}
go(l, m, left);
go(m + 1, r, right);
}
vector<int> restore_permutation(int n, int w, int r) {
N = n;
init(0, N - 1);
compile_set();
vector<int> v(N);
for (int i = 0; i < N; i++) v[i] = i;
f.resize(N);
go(0, N - 1, v);
return f;
}
