#include "messy.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
vector <int> sol;
#define DEBUG 0
void dodaj(int lo, int hi, string s) {
if (lo==hi) return;
int mid=(lo+hi)/2;
for (int i=lo; i<=mid; ++i) {
s[i]='1';
#if DEBUG
printf("dodajem %s\n", s.c_str());
#endif
add_element(s);
s[i]='0';
}
for (int i=mid+1; i<=hi; ++i) s[i]='1';
dodaj(lo, mid, s);
for (int i=mid+1; i<=hi; ++i) s[i]='0';
for (int i=lo; i<=mid; ++i) s[i]='1';
dodaj(mid+1, hi, s);
}
void pitaj(int lo, int hi, string s, vector <int> v) {
if (lo==hi) {
sol[v[0]]=lo;
return;
}
int mid=(lo+hi)/2;
vector <int> v1, v2;
for (int i:v) {
s[i]='1';
int curr=check_element(s);
#if DEBUG
printf("pitam: %s -> %d\n", s.c_str(), curr);
#endif
if (curr) v1.pb(i);
else v2.pb(i);
s[i]='0';
}
for (int i:v2) s[i]='1';
pitaj(lo, mid, s, v1);
for (int i:v2) s[i]='0';
for (int i:v1) s[i]='1';
pitaj(mid+1, hi, s, v2);
}
vector<int> restore_permutation(int n, int w, int r) {
string poc="";
vector <int> vpoc;
for (int i=0; i<n; ++i) poc+='0';
for (int i=0; i<n; ++i) vpoc.pb(i);
sol.resize(n, -1);
dodaj(0, n-1, poc);
compile_set();
pitaj(0, n-1, poc, vpoc);
return sol;
}
