#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#include "messy.h"
void dfs(int l, int r, int n){
if(l == r)return;
string s = "";
for(int i = 1; i <= n; i++){
s += (i < l || i > r ? '1' : '0');
}
int mid = (l + r) >> 1;
for(int i = 1; i <= mid; i++){
s[i - 1] = '1';
add_element(s);
s[i - 1] = '0';
}
dfs(l, mid, n);
dfs(mid + 1, r, n);
}
vector<int> ans;
void dfs(int n, int l, int r, string s){
if(l == r)return;
n = sz(s);
vector<int>L, R;
for(int i = 1; i <= n; i++){
if(s[i - 1] == '1')continue;
s[i - 1] = '1';
if(check_element(s))L.push_back(i); else R.push_back(i);
s[i - 1] = '0';
}
if(sz(L) == 1){
ans[L[0] - 1] = l - 1;
ans[R[0] - 1] = r - 1;
}
int mid = (l + r) >> 1;
for(auto it : L){
s[it - 1] = '1';
}
dfs(n, mid + 1, r, s);
for(auto it : L){
s[it - 1] = '0';
}
for(auto it : R){
s[it - 1] = '1';
}
dfs(n, l, mid, s);
}
vector<int> restore_permutation(int n, int w, int r){
dfs(1, n, n);
compile_set();
string s;
for(int i = 1; i <= n; i++)s.push_back('0');
ans.resize(n);
dfs(n, 1, n, s);
return ans;
}
