#include "messy.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
vector <int> per;
map <pii, vector <int>> which, which2;
void insertit(int l, int r, int n){
if(l == r-1) return;
int mid = (l+r) >> 1, i;
string in = "";
for(i = 0; i < n; i++)
in += "1";
if(l == 0 && r == n-1){
for(i = 0; i < n; i++)
in[i] = '0';
for(i = l; i <= mid; i++){
in[i] = '1';
add_element(in);
// cout << in << endl;
in[i] = '0';
}
for(i = 0; i < n; i++)
in[i] = '1';
}
int mid2;
mid2 = (l+mid) >> 1;
for(i = l; i <= mid; i++)
in[i] = '0';
for(i = l; i <= mid2; i++){
in[i] = '1';
add_element(in);
// cout << in << endl;
in[i] = '0';
}
for(i = l; i <= mid; i++)
in[i] = '1';
mid2 = (mid+1+r) >> 1;
for(i = mid+1; i <= r; i++)
in[i] = '0';
for(i = mid+1; i <= mid2; i++){
in[i] = '1';
add_element(in);
// cout << in << endl;
in[i] = '0';
}
for(i = mid+1; i <= r; i++)
in[i] = '1';
insertit(l, mid, n);
insertit(mid+1, r, n);
}
void find(int l, int r, int n, int pl = 1, int pr = 4654646){
if(l == r) return;
int mid = (l+r) >> 1, i;
string in = "";
for(i = 0; i < n; i++)
in += "1";
if(l == 0 && r == n-1){
for(i = l; i <= r; i++)
in[i] = '0';
for(i = l; i <= r; i++){
in[i] = '1';
//cout << in << endl;
if(check_element(in)){
// cout << i << endl;
which[mp(l, r)].pb(i);
}
else
which2[mp(l, r)].pb(i);
in[i] = '0';
}
for(i = l; i <= r; i++)
in[i] = '0';
}
else{
if(l == pl){
for(i = 0; i < sz(which[mp(pl, pr)]); i++){
in[which[mp(pl, pr)][i]] = '0';
}
for(i = 0; i < sz(which[mp(pl, pr)]); i++){
auto to = which[mp(pl, pr)][i];
in[to] = '1';
//cout << in << endl;
if(check_element(in)){
which[mp(l, r)].pb(to);
// cout << to << endl;
}
else{
which2[mp(l, r)].pb(to);
}
in[to] = '0';
}
for(i = 0; i < sz(which[mp(pl, pr)]); i++){
in[which[mp(pl, pr)][i]] = '1';
}
}
else{
for(i = 0; i < sz(which2[mp(pl, pr)]); i++){
in[which2[mp(pl, pr)][i]] = '0';
}
for(i = 0; i < sz(which2[mp(pl, pr)]); i++){
auto to = which2[mp(pl, pr)][i];
in[to] = '1';
// cout << in << endl;
if(check_element(in)){
which[mp(l, r)].pb(to);
// cout << to << endl;
}
else{
which2[mp(l, r)].pb(to);
}
in[to] = '0';
}
for(i = 0; i < sz(which2[mp(pl, pr)]); i++){
in[which2[mp(pl, pr)][i]] = '1';
}
}
}
// cout << l << ' ' << r << endl;
find(l, mid, n, l, r);
find(mid+1, r, n, l, r);
}
vector<int> restore_permutation(int n, int w, int r) {
per.resize(n, -1);
insertit(0, n-1, n);
compile_set();
find(0, n-1, n);
for(int i = 0; i < n; i += 2){
//cout << which[mp(i, i+1)].size() << ' ' << which2[mp(i, i+1)].size() << endl;
// cout << which[mp(i, i+1)].back() << ' ' << which2[mp(i, i+1)].back() << endl;
per[i] = which[mp(i, i+1)].back();
per[i+1] = which2[mp(i, i+1)].back();
}
return per;
}
